Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!ncar!oddjob!uxc!uxc.cso.uiuc.edu!a.cs.uiuc.edu!m.cs.uiuc.edu!wsmith
From: wsmith@m.cs.uiuc.edu
Newsgroups: comp.lang.misc
Subject: Re: Random permutation algorithm
Message-ID: <5200014@m.cs.uiuc.edu>
Date: 22 Aug 88 11:55:00 GMT
References: <5200012@m.cs.uiuc.edu>
Lines: 42
Nf-ID: #R:m.cs.uiuc.edu:5200012:m.cs.uiuc.edu:5200014:000:1705
Nf-From: m.cs.uiuc.edu!wsmith    Aug 22 06:55:00 1988




This is an example of why informal specifications are not always the
best.  If the problem that was meant to be described and the problem
that was described in responses to this discussion are put next to each other, 
they don't match.  The specification says that the random integers are drawn 
from 1 to n, while the implementation draws the integers from [i..n].  
     ^							       ^
These are not the same thing.


#
#    Problem: Random Permutation
#
#    Description: Given n and a sequence of n integers drawn independently
#                 from a uniform distribution over 1..n, produce a uniformly
			 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
#                 random permutation of the sequence 1..n.

>	for i from [1...n] sequentially chosen
>	  select j from [i...n] randomly
			^^^^^^^
>	  exchange a(i),a(j)
>	  end loop

I would vote that the informal specification does not specify the intended
problem.  I propose that instead of selecting n integers drawn from
1..n, the problem specifiction only require that the product of the ranges of 
the selected numbers equal n!.   I think that, if it were correct, the original
specification is biased to the imperative language's implementation.

     Proposed problem definition:
<    Description: Given n and a sequence of integers selected from a
<                 uniform distribution of 1 to m[i] for the ith integer,
<		  subject to the constraint that the product of the m[i]'s
<		  equals n!, produce a uniformly random permutation of the 
<		  sequence 1..n.

The problem requires the numbers being shuffled to be the numbers 1 to n
and that the amount of "randomness" used to be a minimum.

Bill Smith		wsmith@cs.uiuc.edu		uiucdcs!wsmith