Re: not enough real programmers?

[dpeschel@u.washington.edu (Derek Peschel)]

In article <37AEA89C.E6088226@abg1.siemens.de>,
Volker Hetzer  <volker.hetzer@abg1.siemens.de> wrote:
>Everett M. Greene wrote:

>> > 4.  "Write a program to perform a "perfect shuffle" on an array of 52
>> > numbers."
>> 
>> Anybody with a good answer to question 4 doesn't need to be interviewing
>> for a job.  There are any number of companies, academic institutions,
>> etc. who would like a definitive answer to that problem.
>If perfect means "all permutations are equally likely", then Knuth has an answer.
>Without having read it, I'd simply use a random number generator to put cards
>from one array into the other (modulo the remaining cards, etc.). It should give
>a shuffle as good as the random number generator.

You overlooked a problem.  (I didn't realize this when I read the original
challenge, but I did realize it as soon as someone pointed out that the
challenge is vague.)

The problem is that "perfect shuffle" might not mean "perfectly random
shuffle" but instead "shuffle with perfect interleaving".  In particular,
you can do an "ideal" shuffle by dividing the cards into two piles and then
using cards from altnerating piles to create the shuffled deck.  It's like
what happens when you shuffle cards as usual, except that the cards never
fall in clumps, only one at a time in perfect altneration.

Eight (?) of those operations will leave the deck as it originally was.  So
as you can see, it's not very random.  But it is easy to program.

-- Derek