Shuffling a random array

Question

Looking for some help regarding a shuffle and cryptogram problem in java.

First, I tried to randomly shuffle a array, but i keep getting 2 of the same values in the shuffled array.

Here's the code :)

public static void shuffle (char[] characterArray) {
  Random generator = new Random(12345);
  for (int i= 0; i<characterArray.length ; i++) {       
    int numberChoosen = generator.nextInt(characterArray.length);        
    System.out.print((characterArray[numberChoosen]));
  } 
}

As you can see, for an characterArray of {A,B,C,D}, the code generate a shuffled array that looks like {B,C,D,D}.... Why does it generate two D's instead of 1 letter for each letter in the original array?

Thanks! :)

You could also make a comparator that compares two random values generator bij de `Random` class. Then you do `Collection.sort(array, random_comparator)`. However `Collections.shuffle` is the standard solution. — martijnn2008, Oct 25 '15 at 12:42
@martijnn2008 no. A comparator must be consistent. It can't return random values. — JB Nizet, Oct 25 '15 at 12:44
@JBNizet Why wouldn't it work. You can make a standard comparator, but instead of comparing the two values you compare the two newly generator random values. So, please say 'I don't understand your solution' instead of 'It's not possible'. — martijnn2008, Oct 25 '15 at 12:45
It wouldn't work because it would break the contract of Comparator on which sort() relies. The sort algorithm could detect it and throw an exception. It could also not detect it and go into an infinite loop. Anything could happen, since you're violating the preconditions. I never said it was impossible, and I do understand your solution. BTW, the javadoc of sort says: *IllegalArgumentException - (optional) if the comparator is found to violate the Comparator contract.* — JB Nizet, Oct 25 '15 at 12:47

score 2 · Answer 1 · edited May 23 '17 at 10:27

Your use of Random doesn't prevent an entry from being chosen more than once. If you are looking to simply randomize the order of the array, you may be well advised to generate a new array, populating it with the entries from the old one - removing one entry from the old at a time to create the new one.

Since array sizes are not mutable in Java, you may need to use some additional or an alternate data structure to keep track of which entries have already been returned.

A number of approaches that can be used to do this are available at Random shuffling of an array - complete with source code.

You could try something like this:

public static void shuffle(char[] characterArray){
    final List<Character> charList = new ArrayList<>(characterArray.length);
    for(final char c : characterArray){
        charList.add(c);
    }
    Collections.shuffle(charList);

    for(final char c : charList){
        System.out.print(c);
    }
}

The single-argument Collections.shuffle call internally creates and uses a new Random(). However, if you must "use" / show use of the Random class (or use an alternate source of randomness):

public static void shuffle(char[] characterArray){
    final Random generator = new Random(12345);

    final List<Character> charList = new ArrayList<>(characterArray.length);
    for(final char c : characterArray){
        charList.add(c);
    }
    Collections.shuffle(charList, generator);

    for(final char c : charList){
        System.out.print(c);
    }
}

Now, I wouldn't use the single-argument Random constructor with a constant value, if you're looking for unpredictable outputs here.

Alternatively, you could follow the above suggestions in terms of approach to do something similar yourself without calling Collections.shuffle. Reviewing the source code of Collections.shuffle yourself could also be educational.

sorry, i don't think i understand what you are trying to say. How would you implement the solution you tagged in your comment to my code? — Jenna, Oct 25 '15 at 03:07
@Jenna - please see the sample that I just added to the answer. — ziesemer, Oct 25 '15 at 03:20
Awesome! However, what if i told you that I absolutely have to use the Random class to achieve it. How is your sample code changing if we take that constraint into consideration? :) thx — Jenna, Oct 25 '15 at 03:50
@Jenna - Is this homework? Regardless, please see the updates to the answer. — ziesemer, Oct 25 '15 at 12:26

score 1 · Answer 2 · answered Oct 25 '15 at 12:44

The standard algorithm for shuffling an array is the Fisher-Yates shuffle, also known as 'Algorithm P' from Knuth. Unless you have a good reason not to use it, use Fisher-Yates.

If you are looking at a cryptographic use then you will need to use a cryptographically secure random number generator such as Java's SecureRandom. Do not use the standard insecure RNGs, which are fine statistically but very insecure cryptographically.

Shuffling a random array

2 Answers2