Shuffle Algorithm

[left1none]

I know of some ways to possibly do this but what is the absolute best way to do a totally random shuffle. I want the odds to be close to a real shuffle. Thanks.

Jack

[wsmmi6674]

Assuming a "perfect" randomization function, here is some pseudo code that will return a random item from an array, one at a time, until the array is exhausted:

Initialization:
Fill an array with objects in any order.

To fetch the next object:
As long as there are objects left in the array:
Choose a random object from the array.
Move the element in the last slot in the array to the slot formerly occupied by the object selected in the previous step.

When the array is exhausted:
Perform the initialization step again.

If you absolutly must have an array in a shuffled state, use the above algorithm to create one from a non-shuffled array.

Your last statement is more interesting, however: "I want the odds to be close to a real shuffle". A real (ordinary) shuffle by a human does not produce a truly random ordering. If this is what you are trying to replicate, then more complicated algorithms are needed.
--
Scott

[RoboTact]

it can be done in-place, if you'll swap selected element and the last in consideration:

template<elem>
void shuffle(vector<elem> &arr)
{
  for(int n=arr.size();n>1;n--)
  {
    int rand_ind=random(0,n-1); // function returns element in [0,n-1], it may be rand()%n.
    swap(arr[rand_ind],arr[n-1]);
  }
}

There is std::random_shuffle function (template), but it's rather obfuscated.

[wsmmi6674]

it can be done in-place, if you'll swap selected element and the last in consideration

Of couse! How silly of me. Note that your construction of selecting the next item to swap:

int rand_ind=random(0,n-1);

Is correct, unlike:

int rand_ind=random(0,arr.size()-1);

Which will not produce an even distribution.
--
Scott

[left1none]

Your last statement is more interesting, however: "I want the odds to be close to a real shuffle". A real (ordinary) shuffle by a human does not produce a truly random ordering. If this is what you are trying to replicate, then more complicated algorithms are needed.
--
Scott

I don't know if this is entirely true. A trained human can shuffle cards more randomly than a computer can. At least most of the algorithms I have seen. I actually am a dealer at a casino. And some people may not shuffle to good but most casinos design ways to make it more random. But compared to a computer I think it is more random. Thanks for all the feedback guys.

Jack

[RoboTact]

It depends on definition of "randomness" of shuffle. How do you tell which shuffle is more random? Given algorithms shuffles to any permutation with equal probability.
And given "non-standard" definition of "more random" shuffle, you can write a programm which would do it better. But notice that I would assume it cheating if shuffle would be non-standard.

[wsmmi6674]

I don't know if this is entirely true. A trained human can shuffle cards more randomly than a computer can. At least most of the algorithms I have seen. I actually am a dealer at a casino. And some people may not shuffle to good but most casinos design ways to make it more random. But compared to a computer I think it is more random. Thanks for all the feedback guys.

It depends on how you define the terms. Assuming a perfect random function, either Robo's or my algorithm results in a completly random distribution. The best a human could do is equal it. A dealer performing the usual two or three riffles and a couple of monge's will not completly randomize the deck. Of course, perfect random functions on computers are hard to come by, too.

What game(s) do you deal? Aren't most casino's going to automatic shufflers these days?
--
Scott

[left1none]

What game(s) do you deal? Aren't most casino's going to automatic shufflers these days?
--
Scott

I deal blackjack, three card poker, crazy 4 poker, carribean stud, 21+3, Let it ride,
Spanish 21, boston 5 stud. I think that's it. All the games except blackjack are shufflers. We do have a few auto shufflers for blackjack but only the $5 tables. I guess to get more hands per hour out since it makes less money. Even in the poker games where there is a shuffler we are still shuffling the cards before putting them in. I figured because because it isn't as random either. It's just a computer as well. Thanks for all the feedback.

Jack

[RoboTact]

Even in the poker games where there is a shuffler we are still shuffling the cards before putting them in. I figured because because it isn't as random either. It's just a computer as well. Thanks for all the feedback.

It's more random then anything else. Pre-shuffling is useless if shuffling algorithm is sane (though it obviously can't lower the quality of shuffling). The only problem you can get is that somebody would influence that shuffling machine...

[NMTop40]

The problem with computer-generated random deals is the generator can only be seeded with 2^32 different values which is lower than the 52! possible permutations (about 2^225.581)

If you can improve the random generator to give a truly random sequence then it would be fine.

[wsmmi6674]

The problem with computer-generated random deals is the generator can only be seeded with 2^32 different values which is lower than the 52! possible permutations (about 2^225.581)

If you can improve the random generator to give a truly random sequence then it would be fine.

This assumes you are using the language's built-in random function (i.e. rand() for c++). There are plenty of algorithms available for an acceptable n-bit pseudo random number generator. And if that's not good enough, there are hardware solutions that give a truly random bitstream. I'm not entirely sure how this is done, but I believe some of them involve random decay rates of some innocuous materials.