CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Aug 2000
Posts
18

## random shuffle

Does anybody have a fast routine to do a random shuffle of an array of integers? I have looked at the random_shuffle template, but I want to shuffle the array itself, rather than vectors. I have been using the rand() function then using a modulus to pick a random entry and then swapping memory. It works, but I can't help thinking that there must be a faster way.

thanks

2. Senior Member
Join Date
Nov 1999
Location
Dresden / Germoney
Posts
1,402

## Re: random shuffle

From inquiry.com:
&gt;&gt;&gt;&gt;
Using random_shuffle() with Built-in Arrays
You shouldn't be concerned about the overhead of using containers instead of built-in arrays. All STL algorithms apply to sequences, not just containers. Thus, you can use random_shuffle() with built-in arrays as well. Make sure that the second argument of random_shuffle() points one element past the array bounds:

char carr[4] = {'a', 'b', 'c', 'd'};
/*carr+4 points one position past array bounds*/
random_shuffle(carr, carr+4);
for (int i = 0; i &lt; 4; i++)
cout&lt;&lt;carr[i]; /* display shuffled elements */

However, it depends on the actual STL implementation how fast it is.

A simple algorithm to shuffle N integers a[0]..a[N-1]:
pick an random number r from [0..N-1]
swap a[r] with a[N-1]
N=N-1 and repeat until N reaches 1

(I haven't tested it, I just proved it correct ;-)

3. Junior Member
Join Date
Aug 2000
Posts
18

## Re: random shuffle

The simple routine at the end of your post was the same way I originally coded mine, but I hoped that something else would be faster. I needed to shuffle an array many times to test a simulation. When I tested the template class, it was exactly the same speed as my original routine. (49 seconds to shuffle a deck of cards 5 million times on 500 mHz P3)

thanks

4. Senior Member
Join Date
Nov 1999
Location
Dresden / Germoney
Posts
1,402

## Re: random shuffle

Hi,

No, As much as I meditated about it, there is no faster algorithm - unless you want to sacrifice some randomness.

5 million shuffles in fifty seconds sounds relatively cool - but I don't know what you need.

I assume you already switched to a release build, and perhaps played with the optimization options a bit, if so you could just eval some low level optimizations - but only if it#s woth the trouble. I could imagine using an inlined rand() replacement (one of the x=(a+x)%b generators should be perfect, if you re-shuffle the previous table you need no extra shuffle table) Check Knuth for good values of a and b.

If you don't know if your snipped is "optimal" (mostly it is if you don't do something blatantly wrong with nowadays compilers), just post it.

Good luck.
Peter

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•