Java: Generate the alphabet in random order, no duplicates

[-Noah-]

Hi guys,

I am taking an introductory programming course and need a bit of help. The assignment is to have the Java program read a message (I am assuming from a .dat file, not quite sure). The program creates substitutes each random letter with a different letter chosen at random by the computer. If the letter M is chosen to replace the letter P in the message, then M replaces P in every instance of the message.

Right now, I just need help with generating a set of the 26 letters ordered randomly without duplicates. Here is what I have:

import java.util.Random;

public class encrypt {

public static void main(String[] args) {

char [] alphabet =

{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

char [] substitute =

{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

boolean done=false;

Random generator = new Random();

int i, j, k, random;

while(done==false) {

for(i=0; i<=25; i++) {

random = generator.nextInt(25);

substitute=alphabet[random];

for(j=0; j<=i; j++) {

while(substitute[j]==substitute) {

random = generator.nextInt(25);

if(substitute[j]!=substitute) {

substitute=alphabet[random];

}

}

}

}

for(k=0; k<=25; k++) {

System.out.print(substitute[k] + ", ");

}

done=true;

}

}

}

Right now the program does nothing. If I remove the last for loop with j as the counter and everything within that for loop, I get an output of 26 letters randomly chosen, but there are duplicates. The last for loop is supposed to say something like, "If the randomly generated letter (substitute) has appeared before in substitute[], then generate a new random number until it is no longer a duplicate of a previous number, at which point the letter which corresponds to the random number is stored in substitute.

So if you could give me some suggestions it would be much appreciated. If I am overcomplicating things and there is a much easier way to do this, please guide me in the right direction.

Thanks,

Noah

EDIT: Spacing in the program code isn't working. Looks fine while I'm editing it though. What's wrong?

EDIT 2: See here for my code, correctly formatted.

Edited May 26, 2009 by -Noah-

[Zapadlo]

Your way seems a little strange unless I am missing something. Why don't you just have an array for the alphabet and then just pick a letter at random when you need it. From what I understood you don't actually need an entire randomised alphabet.

[-Noah-]

Your way seems a little strange unless I am missing something. Why don't you just have an array for the alphabet and then just pick a letter at random when you need it. From what I understood you don't actually need an entire randomised alphabet.

Thanks for the response.

How would I make sure that I do not pick the same letter from the alphabet array more than once?

[ecstasis]

Thanks for the response.

How would I make sure that I do not pick the same letter from the alphabet array more than once?

removing it would be the easiest way

[Brian M. Veteran]

You could always switch to using a LinkedList instead of an array, when you choose a letter, you just remove it from the list.

The size of the list would decrease each time, so you'd need to generate a random number using the variable linkedlist.size() instead of 25.

[Zapadlo]

I would stick to the array personally and have another with the letters already used so that when a new random letter is picked it is checked against those in the already used array.

LinkedLists - /covers eyes and shrieks

Sorry, personal disposition :)

[ecstasis]

I would stick to the array personally and have another with the letters already used so that when a new random letter is picked it is checked against those in the already used array.

LinkedLists - /covers eyes and shrieks

Sorry, personal disposition :)

why would you want to maintain 2 arrays versus a single shrinking array that will only ever have letters you can use?

not to mention random doesn't mean true random, you could (however unlikely this is) end up randomizing the same already used letter multiple times in a row

[Zapadlo]

why would you want to maintain 2 arrays versus a single shrinking array that will only ever have letters you can use?

not to mention random doesn't mean true random, you could (however unlikely this is) end up randomizing the same already used letter multiple times in a row

I can see what you are saying, and it is true, but I am compelled to say, so?

[shakey_snake]

I can see what you are saying, and it is true, but I am compelled to say, so?

So... then you don't have to compare and try the operation again...

[-Noah-]

That was my problem: I knew there would be a chance that it could generate the same letter again. That's why I made my code the way I did. Also, I don't see how creating a "used letters" array would be any better than my method.

The only problem is, why doesn't my code work!?!?

How would I go about creating a linked list in Java? I looked online and unless I am missing something, it looks pretty complicated.

[Zapadlo]

import java.util.Random;
import java.io.*;
import java.lang.*;
import java.lang.String.*;



public class encrypt {

public static void main(String[] args) {

char [] alphabet =
{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char [] substitute =
{'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char [] used =
{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0'};
boolean done=false;
Random generator = new Random();
int i, j, k, random, count;

count = 0;

System.out.print("Enter a string: ");

	  //  open up standard input
	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	  String input = null;

	  //  read the username from the command-line; need to use try/catch with the
	  //  readLine() method
	  try {
		 input = br.readLine();
	  } catch (IOException ioe) {
		 System.out.println("IO error");
		 System.exit(1);
	  }

	  //loop
	  for (int l = 0; l < input.length(); l++)	{
		  count++;

  }
		  System.out.println(count);

		for(int p = 0; p <count; p++)	{

			int result = 0 + (int) ( Math.random()*(26) );

			char temp = alphabet[result];

			char temp2 = '1';
			int o = 0;
			while(temp2 != '0')	{
			//for(int o = 0; o < used.length(); o++)	{

				temp2 = used[o];

				if(temp == temp2) {					
					result = 0 + (int) ( Math.random()*(26) );
				}
				o++;
			}
			char temp3;
			temp3 = input.chatAt(count); // No idea why this doesn't work
			alphabet[result] = temp3;


			count++;
		}


	  System.out.println(input);


while(done==false) {
for(i=0; i<=25; i++) {
random = generator.nextInt(25);
substitute[i]=alphabet[random];
for(j=0; j<=i; j++) {
while(substitute[j]==substitute[i]) {
random = generator.nextInt(25);
if(substitute[j]!=substitute[i]) {
substitute[i]=alphabet[random];
}
}
}
}
for(k=0; k<=25; k++) {
System.out.print(substitute[k] + ", ");
}
done=true;
}
}
}

Something like that, only charAt doesn't work, sorry I'm tired so if you can fix that part I can check the rest of the code.

Oh and this way you have all the letters you have used in an array for printing/whatever.

So... then you don't have to compare and try the operation again...

All it is, is a for loop running through used array in case you pick a letter that has been already used you just pick a new random letter.

Edit: Actually, it only checks once and if it picks a letter that already occured again it proceeds when it shouldn't.

Also not accounting for spaces... /sigh there is actually quite a lot, hope it helps though.

Edited May 26, 2009 by Zapadlo

[micro]

Just make an array filled with char's of the alphabet and have he index of the array be printed out by generating random numbers in a for loop.

[The Teej]

why would you want to maintain 2 arrays versus a single shrinking array that will only ever have letters you can use?

not to mention random doesn't mean true random, you could (however unlikely this is) end up randomizing the same already used letter multiple times in a row

Because LinkedLists seem a bit advanced for someone doing basic stuff like this in an introduction to a java course. Anyway:

Seems pretty sloppy (but it's 12:35am), but here it is. It's commented and stuff so you actually have a clue on what's going on. BTW, did you know you can declare variables while in for-loops? You don't need to declare "int i" as a member variable if you're just going to use it for for loops. Java should also just destroy the integer once you're out of the for loop, meaning you can reuse int i in another for loop if you so wish.

import java.util.Random;

public class encrypt {
  public static void main(String[] args) {
	char [] alphabet =  {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	char [] substitute = {'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.'};  //this should be 26 dots, please check
	int [] numbers = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};  //this should be 26 zeros, please check to see if this correct!!

	for (int i=0; i<=25; i++) {
	  random = generator.nextInt(25);
	  //keep running this if-else until we find a number we haven't used before
	  do {
		//if we find a number we haven't used before
		if (numbers[random] == 0) { 
		  numbers[random] = random; //then assign that position in the array that number (i.e. position 10 in the array will now have the number 10)
		  substitute[i] = alphabet[random];  //assign the current position of the substitute alphabet array the random letter from the real alphabet
		}
		else {
		  random = generator.nextInt(25); //if we hit a number we've already used, get another one
		}
	  } while (numbers[random] != 0)
	}
	for(int i=0; i<=25; i++) {
	  System.out.print(substitute[i] + ", "); //print out your brand new randomised alphabet!
	}
  }
}

I'll admit, I have no idea if this works or not, as I don't have the java compiler on my computer any more (haven't done java in about a couple of years), but this should work. There's no harm in compiling it yourself though, just shout out any errors if there are any.

[ecstasis]

heres my attempt, not compiled but i don't imagine its too far off (could be wrong tho)

private String jumble(String[] original) {
	Random gen = new Random();
	String[] alphabet = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "x", "y", "z", " "};
	ArrayList alphabetaGenList = new ArrayList(Arrays.asList(alphabet));
	Hashtable newAlphabet = new Hashtable();
	StringBuffer jumbled = new StringBuffer();
		int randomAlphabetLetter = 27;

		//oops made a mistake with the random, 2nd edit
	for (int i = 0; i < 27; i++) {
				int r = gen.nextInt(randomAlphabetLetter--);
		newAlphabet.put(alphabet[i], alphabetGenList.get(r));
		alphabetGenList.remove(r);
	}

	for (int i = 0; i < original.length; i++) {
				jumbled.append(newAlphabet.get(original[i]));
	}	

	return jumbled.toString();
}

edit...

i guess thats a bit overkill since it converts the string too, but not many changes just to do the alphabet

Edited May 27, 2009 by ecstasis

[-Noah-]

Thanks guys for all the replies.

Zapadlo: I don't know if you realized this, but you have chatAt instead of charAt. :p Even with that change, it throws an error:

Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 5

at java.lang.String.charAt(Unknown Source)

at encrypt.main(encrypt.java:66)

The string index out of range value is always the number of characters that I have typed for the string. I'm guessing my code at the bottom was not supposed to be there. No problem, though. I live in the US, so it's quarter of 10 now. Didn't mean to give you guys Java code problems in the middle of the night! Is Neowin UK based?

-Noah

[-Noah-]

Teej: I added a semicolon after the while statement. No errors, but here are some examples of the output:

Output 1. W, C, U, H, E, D, F, Q, A, ., T, K, ., ., J, ., X, ., L, ., R, ., O, ., ., .,

Output 2. V, ., P, ., H, K, Q, ., D, S, ., ., G, J, R, F, N, ., M, B, ., Y, ., ., W, U,

Output 3. X, O, W, I, P, ., U, G, Q, R, F, ., ., V, A, B, ., ., K, ., Y, H, ., E, T, M,

I cant figure out what is wrong, most likely because I don't exactly know what is going on with the do while. Does the while statement at the end tell the program to go through the do again under the specified conditions? If you have any more ideas for fixing this, they are welcome!

About the int within the for-loop, my teacher says that it wastes memory and that you should define those variables first, out of the for-loop (?). I'm guessing she's wrong. :laugh:

[ecstasis]

About the int within the for-loop, my teacher says that it wastes memory and that you should define those variables first, out of the for-loop (?). I'm guessing she's wrong. :laugh:

i'm not sure it would make a difference either way since those variables would go to the garbage collector once they are out of scope (i don't know exactly how java deals with).

[Tech God]

These solutions are all overkill...

- Make an ArrayList containing all 26 letters.

- generate random number from 0 to List.size()-1.

- List.get(randomNumber)

- List.remove(randomNumber)

loop and restart at step 2 until List.size() returns 0.

import java.util.*;

class alphaRandom {

	public static void main(String[] args) {

	ArrayList<Character> al = new ArrayList<Character>();
	Random gen = new Random();
	int num;

	for(int i = 65; i <= 90; i++) {
		al.add((char)i);
	}

	while(al.size() > 0) {
		num = gen.nextInt(al.size());
		System.out.print(al.get(num));
		al.remove(num);
	}
 }
}

Edited May 27, 2009 by Tech God

[Sikh]

I had to do this for school too.

Stick to your method of arrays. LinkedLists are a pain for this.

I say keep 1 array list(alphabet).

Then create a random number from 0 - array.length()-1

after that just loop thru and remove the letter that your random number is. Havent done java in a few months so I dont know the EXACT array command to say "array.get? or etc".

Idk, but logically I would do it this way. Easier.

[Brian M. Veteran]

These solutions are all overkill...

- Make an ArrayList containing all 26 letters.

- generate random number from 0 to List.size()-1.

- List.get(randomNumber)

- List.remove(randomNumber)

loop and restart at step 2 until List.size() returns 0.

import java.util.*;

class alphaRandom {

	public static void main(String[] args) {

	ArrayList<Character> al = new ArrayList<Character>();
	Random gen = new Random();
	int num;

	for(int i = 65; i <= 90; i++) {
		al.add((char)i);
	}

	while(al.size() > 0) {
		num = gen.nextInt(al.size());
		System.out.print(al.get(num));
		al.remove(num);
	}
 }
}

If you want to same some programming time, al.remove(num) will also return the object it's removing - so System.out.print(al.remove(num)) should work.

[Tech God]

If you want to same some programming time, al.remove(num) will also return the object it's removing - so System.out.print(al.remove(num)) should work.

point taken, thanks, haven't used java in years.

[The Teej]

Teej: I added a semicolon after the while statement. No errors, but here are some examples of the output:

Output 1. W, C, U, H, E, D, F, Q, A, ., T, K, ., ., J, ., X, ., L, ., R, ., O, ., ., .,

Output 2. V, ., P, ., H, K, Q, ., D, S, ., ., G, J, R, F, N, ., M, B, ., Y, ., ., W, U,

Output 3. X, O, W, I, P, ., U, G, Q, R, F, ., ., V, A, B, ., ., K, ., Y, H, ., E, T, M,

I cant figure out what is wrong, most likely because I don't exactly know what is going on with the do while. Does the while statement at the end tell the program to go through the do again under the specified conditions? If you have any more ideas for fixing this, they are welcome!

About the int within the for-loop, my teacher says that it wastes memory and that you should define those variables first, out of the for-loop (?). I'm guessing she's wrong. :laugh:

Haha, I am a complete prat. I've made a couple of changes. Basically, the do-while loop was running the code within the loop while the random number isn't zero, meaning, if the position was being used, then it would generate a random letter until it wasn't being used, hence why you get the odd gaps. This new code does the opposite of this (runs the code within the loop until we get a random letter which isn't being used). I also changed all of the numbers to -1 because we would run into an infinite loop as position 0 would never be allowed.

There are three arrays: the alphabet array, the number array and the substitute alphabet array.

The number array is filled with -1s at the beginning, but as the for loop progresses, the number array gets filled up with numbers between 0-25.

Each time the code goes through the loop, it checks to see if that position in the array isn't -1 (i.e. isn't used), and if it isn't -1, then fill that position in the array with the random number, and then take whatever letter is in that position in the alphabet array, and apply it to the next space in the substitute alphabet array.

If the position in the number array ISN'T -1, then we generate a random number and the do-while loop returns to the beginning and we do the process again.

The do-while keeps doing this until we find a number which isn't -1, at which point, the for loop increments i and we start at the beginning of the code within the for-loop.

import java.util.Random;

public class encrypt {
  public static void main(String[] args) {
	char [] alphabet =  {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	char [] substitute = {'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.'};  //this should be 26 dots, please check
	int [] numbers = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};  //this should be 26 -1s, please check to see if this correct!!

	for (int i=0; i<=25; i++) {
	  random = generator.nextInt(25);
	  //keep running this do-while until we find a number we haven't used before
	  do {
		//if we find a number we haven't used before
		if (numbers[random] == -1) { 
		  numbers[random] = random; //then assign that position in the array that number (i.e. position 10 in the array will now have the number 10), so it's considered to be used
		  substitute[i] = alphabet[random];  //assign the current position of the substitute alphabet array the random letter from the real alphabet
		}
		else {
		  random = generator.nextInt(25); //if we hit a number we've already used, get another one
		}
	  } while (numbers[random] == -1);
	}
	for(int i=0; i<=25; i++) {
	  System.out.print(substitute[i] + ", "); //print out your brand new randomised alphabet!
	}
  }
}

Also, as for what your teacher says, what the hell? Forgive me if I'm wrong, but I'm really certain Java's automatic trashing would destroy the integer as soon as we get outside of the for loop, as opposed to at program termination, meaning it's more efficient to do it that way in this particular instance. Unless you need to use that specific integer value for another task outside of the for loop, declaring it outside of there is pointless.

Regardless of whether it trashes it or not after the for loop, though, it just makes the code neater to actually create the integer for a for-loop in the for-loop, instead of at the beginning, when it may not be needed at all. This is especially true if you have a for-loop within an if-else (as the for-loop may never be executed, meaning you've just wasted memory on declaring an integer which won't be used), or if you're using for-loops in object oriented code, which may not be called very often. Also, if you're using quite a few for loops, you don't want to have to do something like:

int i = 0;	//this integer is for a for loop that does this
int j = 0;		 //this integer is for a for-loop that does that
...
int l = 0;	//this integer is for yet another for-loop that does this thing somewhere in the code, I forget where it is now

Edited May 27, 2009 by The Teej

[JamesCherrill]

int variables are primitive types, not Objects and are not created on the heap or garbage collected. They are allocated on the stack when coming into scope and thus released then they go out of scope. Teacher is talking rubbish - an int occupies the same space on the stack wherever it is defined, it just occupies that space for less time when its scope is smaller. And is anyone seriously worrying about 4 bytes of memory in 2009?

[Andre S. Veteran]

Obviously the teacher is thinking about :

for (blabla) {
	Object o = new Object();
}

vs

Object o = new Object();
for (blabla) {
}

Here the latter is more efficient since Object() is allocated and constructed only once. If you can move any initialization out of a loop, it's always more efficient to do so. However, doing :

Object o;
for (blabla) {
	o = new Object();
}

is no performance improvement as the object still needs reallocation and construction each time through the loop. The reference o itself is statically allocated, i.e. it's merely a stack pointer increment at the beginning of the method and a decrement at the end, it makes no difference where you declare it in the method.

As for primitive types like int, there is no allocation and no construction involved, so from a performance standpoint it doesn't matter where they are declared within a method. Actually one should try to reduce the scope of variables as much as possible, so here declaring it inside the loop is what makes the most sense since that's the only place where it's supposed to be accessible.

In C++ the question might be different (and I'm unsure about the details), but here we're talking about Java not C++.

Show this to your teacher. :p

[sialivi]

- List.get(randomNumber)

- List.remove(randomNumber)

No need to do this in two steps, the remove method returns the Object it removes so the get method call can be skipped

[Tech God]

No need to do this in two steps, the remove method returns the Object it removes so the get method call can be skipped

thanks for repeating what someone else said captain obvious