randomizing an array

If you're using C++, you can use std::random_shuffle.

I'm using java

I think you'll still have to use an algorithm that runs through the whole lot, even if you have three million of them. Run through in order and for each one in normal order, swap it with one other randomly selected one.

but how do i know if the one in random order is not used before

Quote:

Original post by gorgorath but how do i know if the one in random order is not used before

I take it you mean you don't want to re-order an element thats already been re-ordered.

1. This is slower, because you have to make an additional check.
2. It doesn't matter, random means random. I think you would be making your algorithm 'less random' by doing the additional check. At the very least its not an improvement.

It doesn't matter - it is still a random order. How do you know when you shuffle a deck of cards that a card you are shuffling hasn't been shuffled before?

The only alternative I can see would be to create another array of empty spaces then copy each item from the original list into a random space in the new array, first checking the random space selected hasn't been used but then you have potential indefinate postponement.

Perhaps there is some clever maths algorithm for this I don't know about.

[EDIT] Sorry Dabooksha. Just behind you.

See here for a description of a common and uniformly distributed shuffling algorithm (second paragraph in section). Another link in there goes to here which then links to implementations in both C and Java (you'll have to scroll down a wee bit, or search for "Shuffling an array").

Collections.shuffle

Collections.shuffle(yourLargeList, new Random());

So let me get this straight - You DO have to make that extra check to get a perfectly uniform distribution? I dont get it.

Quote:

Original post by DaBookshah So let me get this straight - You DO have to make that extra check to get a perfectly uniform distribution? I dont get it.

You pass through the list exactly once, there is nothing extra going on.

That shuffle is as good as you're going to get...you have to pass through each location at least once because to do otherwise would be to guarentee that certain positions won't move. This would eliminate a sizeable chunk of the possible permutations, which you most certainly don't want.

Or you could just use Collections.Shuffle. Hopefully, the good folks at Sun are smart enough to have read the material on random shuffles and have implemented a good one.

CM

standard reference of mine for the algorithm.

But yeah, just use the standard library. :)

Quote:

Original post by Zahlman standard reference of mine for the algorithm. But yeah, just use the standard library. :)

I can't stand that site, because there's way too much noise you sift through. While much of the discussions are extremely interesting, as a reference I find it falls pretty short.

However, in this case it does have one extremely useful passage that makes the Knuth shuffle really fall into place:

Quote:

These solutions only serve to illustrate that if you have a perfect random number generator, you have no need to 'shuffle' anything; simply extract a random element from your list of elements as needed. The original problem was: Shuffle a deck of cards in linear time. "Shuffle" could be more realistically defined in terms of human experience as: Use an imperfect random number generator to create a distribution which approximates true randomness. Try doing that in linear time. -- AndyPierce With shuffling, you can't get the same item twice. With a perfect random number generator, you can. Unless "perfect" means "each number comes up exactly once" which means "not very random at all." -- DaveHarris One could use a random number generator, *if* one can "extract" (remove without replacing) a random element in O(1) time. The problem is that most extraction schemes are more like O(N/2) time, where N is the number of elements. (One can probably improve the deletion time, but one also has to be able to efficiently choose a random element. Optimizing both of these seems hard.) -- anon. Actually, this is the insight of the linear shuffle algorithm. If you don't care about corrupting the order of a list (such as the unshuffled cards), you can extract any given element in O(1) time by swapping it out with the final element in the list and decrementing the list size. [This made it all clear - see below.] I wonder if this additional mixing in the "unshuffled" part of the deck could be utilized somehow to decrease the shuffling time to faster than linear? -- AndyPierce

I've always understood what the algorithm does, but now I understand why the algorithm does.

CM