Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Which of below two shuffle algorithms (shuffle1 and shuffle2) is more random?

public final class Shuffle {
    private static Random random;

    public static void shuffle1(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = array.length - 1; i > 0; i--) {
            swap(array, i, random.nextInt(i + 1));
        }
    }

    public static void shuffle2(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = 0; i < array.length; i++) {
            swap(array, i, i + random.nextInt(array.length - i));
        }
    }

    protected static void swap(final Object[] array, final int i, final int j) {
        final Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

The shuffle2 algorithm guaranties that all elements are directly touched, but, in shuffle1 algorithm, the element with index = 0 is never directly touched because of the condition i > 0.

share|improve this question
1  
Welcome to Programmers SE. Please notice that questions cannot be opinion-based, since there would be no response which could concisely answer your question. Consider editing your question in order to ask something which can be answered precisely (an example being, "Which shuffle method is more random?"). –  Neil Sep 19 '13 at 9:01
1  
@Neil, tnx for pointing that out. I've edited the question. –  robosoul Sep 19 '13 at 9:08
    
I'll retract my close vote then. Thanks for fixing that. :) –  Neil Sep 19 '13 at 10:15
    
Make a statistic for a lot of test-runs and analyze the measured distribution, if it satisfies your requirements to 'randomness'. –  MrSmith42 Sep 19 '13 at 11:44
    
@Neil: How do you retract your close vote? I haven't been able to do this on SE (beta) sites where I have high rep. –  Tom Au Sep 19 '13 at 17:11
show 1 more comment

2 Answers

up vote 7 down vote accepted

if you just want a shuffle then use Collections.shuffle(Arrays.asList(array)); which was written by people smarter than you and me.

as for the guarantee that the first element gets touched consider that in the second algorithm the last step (when i==array.length-1) that you are calling random.nextInt(1) which always return 0 which makes that step meaningless

beyond that the algorithms are equivalent

share|improve this answer
2  
@ratchet_freak, I appreciate your answer, but there's no need to be rude. I know that guys who wrote shuffle algorithm are probably smarter than I'm, but that wasn't my question. Second I want to shuffle array, but in an efficient way, and your solution is not, since first I convert array to list, then inside shuffle method it gets converted to array that gets shuffled, and after shuffle i need to convert it back to array. –  robosoul Sep 19 '13 at 10:13
3  
@robosoul the asList just provides a fixed length facade where each set gets propagated back to array. The returned list there implements randomAccess so shuffle doesn't convert back to an array and shuffles in-place. Told you they were smart ;) –  ratchet freak Sep 19 '13 at 10:22
2  
@ratchet_freak, nice come back. "Told you they were smart ;)" made me laugh :D Nice one :) Appreciate the extra effort. Thank you :) –  robosoul Sep 19 '13 at 10:30
5  
@robosoul: I don't think ratchet freak was rude, it's a common thing that we say about implementers of core libraries in several languages. Just like saying that your compiler is smarter than you are. Maybe it's a weird idiom and not the nicest, but I don't think that was a personal thing or an assumption based on your code snippet. Then again, maybe I'm wrong and the freak thinks you're a dumbass. –  haylem Sep 19 '13 at 13:34
add comment

Assuming that your random number generator is sufficiently robust, then the optimal algorithm is the Fisher–Yates shuffle

The algorithm can be summarised as this :-

Given a list of items numbered from 1 to N
Pick a random item between 1 and N and swap with item N
Pick a random item between 1 and N-1 and swap with item N-1
...
Pick a random item between 1 and 2 and swap with item 2.

Of course if the selected item is already in position then there's no need to swap.

The key point is to avoid swapping an item again, once it has been placed in position. See here for a discussion on the bias that can be introduced if you do.

share|improve this answer
    
+1 - for being informative. This doesn't directly answer the OP's question, but it does at a deeper level by pointing out the right way to implement this. –  Stephen C Sep 19 '13 at 9:56
2  
this answer would be complete if you point out that this is exactly what version 1 is –  ratchet freak Sep 19 '13 at 10:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.