Randomize an array?

std::random_shuffle(numbers, numbers+10);

Sorry, but I can't use std::random_shuffle.

Quote:

Notes [1] This algorithm is described in section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms, second edition. Addison-Wesley, 1981). Knuth credits Moses and Oakford (1963) and Durstenfeld (1964). Note that there are N! ways of arranging a sequence of N elements. Random_shuffle yields uniformly distributed results; that is, the probability of any particular ordering is 1/N!. The reason this comment is important is that there are a number of algorithms that seem at first sight to implement random shuffling of a sequence, but that do not in fact produce a uniform distribution over the N! possible orderings. That is, it's easy to get random shuffle wrong.

Well, I don't have that book either. Where can I find this Knuth shuffle algorithm in C?

Look up the implemetation of random_shuffle and use it ;)

Or you could do like this:
for(int i=0;i{
int x = rand_in_range(i,size-1);
swap(a,a[x]);
}

Ok, i have tried it now, seems good at the first look, about the same distribution as random_shuffle of mingw.

[Edited by - Trap on February 26, 2005 11:25:29 AM]

Why would you need the book?

Quote:

Original post by raydog Sorry, but I can't use std::random_shuffle.

I'm curious as to why not? It's part of the STL, meaning it should be available to your C++ environment (#include ).

Wikipedia

From how I read that, Trap's algorithm is one of Knuth's shuffling algorithms, although I'm not sure if its the same one used in random_shuffle.

CM

Quote:

Original post by smart_idiot Why would you need the book?

Well, I can't find any paper describing the algorithm in pseudo-code either. It sounds more complex than just swapping two random array indices.

The question is why you would need to reimplement it rather than using the algorithm in the standard C++ libraries.

In Knuth's shuffling algorithm you can't swap with an element that has already been swapped, otherwise the result will be biased.

The best method would probably be to randomly remove an element from your list, and push it onto a new one, and then once your list is empty swap them back. I think that would ensure they can only be swapped once.

I found a simplier algorithm:
Assign a unique value (GUID) to each array index, and then sort the array indices based on
those unique values.

Is this homework?

No homework today. :)

Unique value per key and sorting sure works, but i don't think it is simpler than the code i posted. It is slower too.

But your code can swap the same element more than once, therefore it's flawed.

Found a very cool RNG to go with your swapping routine:
Mersenne Twister
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

Quote:

Original post by smart_idiot In Knuth's shuffling algorithm you can't swap with an element that has already been swapped, otherwise the result will be biased. The best method would probably be to randomly remove an element from your list, and push it onto a new one, and then once your list is empty swap them back. I think that would ensure they can only be swapped once.

Your change is the same as the original algorithm, it just takes more space.

What's important is that you don't choose from (1, lastCard), but instead from (i+1, lastCard). In otherwords, swap into a position only once. A given card can be swapped several times, so long as it is only moved out of the current position and never into it.

Compare this with your change, and you should see that it's the same. Choose a random card, move it onto the top of your pile. Choose another random card, excluding the ones you've already picked, and move it onto the top of your pile. Repeat until you've chosen all cards once.

This is also faster than the solution raydog has apparently chosen. Linear time rather than logarithmic, because you don't have to sort anything.

CM

Quote:

Original post by smart_idiot But your code can swap the same element more than once, therefore it's flawed.

No, it won't swap the same element twice. If you don't believe me try to prove or disprove it.
My loop invariant is: Elements with index smaller i are random shuffled.

Oh, nevermind. I guess I'm wrong again.

For reference...

(Especially see comments about shuffling 'on demand'. You might find it more natural for your application, and if you happen to have a huge number of things to shuffle, you might want to distribute the work that way.