Re: Random reordering of a list

From: Top Spin (ToppSpin_at_hotmail.com)
Date: 12/05/04 

Date: Sun, 05 Dec 2004 07:51:29 -0800

On 5 Dec 2004 03:58:59 -0800, clemenr@wmin.ac.uk (Ross Clement) wrote:

>Top Spin <ToppSpin@hotmail.com> wrote in message news:<j7f5r0p9dvj502uclnhfq59dqhhvesg3g6@4ax.com>...
>> On Tue, 9 Nov 2004 12:33:05 +1300, "Jeff Miller" <nobody@nowhere.com>
>> wrote:
>> >No, that isn't quite right, intuitive as it appears. To convince yourself
>> >that it isn't right, consider n=3. There are 6 possible orderings, and
>> >you want to make them all equally likely. Now look at
>> >your algorithm: there are 3*3*3=27 equally likely ways it can proceed
>> >(determined by the 3 independent outcomes of the "random" statement).
>> >But 27 isn't evenly divisible by 6, so the 6 possible orderings cannot be
>> >equally likely. Counterintuitive, but evidently true.
>>
>> When I first read your reply, it looked plausible to me. I have since
>> coded it up and run it. It appears to generate an even distribution of
>> the 6 possible permutations.
>
>There are three ways of choosing the first element. For each of these
>choices, there are two ways of choosing the next element. There is
>then one number remaining, so it must be chosen. Hence the number of
>possible ways that the algorithm can proceed is six.

Yes, that's is how the possible permutations are calculated, but
that's not how either algorithm operates.

My algorithm visits each element in the array in ascending order and
swaps it with a random element in the entire array. I have simulated
this algorithm with a few billion iterations and the distribution
looks even.

Jim Clark's algorithm also visits each element in the array except the
first, but in reverse order, and he only swaps it with one of the
unvisited elements. I was concerned that he doesn't explicitly visit
the 1st element, but I also simulated this algorithm and the
distribution also looks even.

>Whether we're choosing the last element in the array, or the first
>element, makes no difference that I can see, apart from the effects
>due to the pseudo-random number generator not being

Yes, I can't see that it matters which direction you go. 

--
Email: Usenet-20031220 at spamex.com
(11/09/04)

Relevant Pages

  • Re: An algorithm questions
    ... Mathieu Dutour -- Doubly linked list in two arrays + a array ... Richard Harter -- The devil's list algorithm ... The storage costs are: ... dependent; I prefer to use unsigned char arrays for that reason; YMMV. ...
    (comp.lang.c)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
  • [SUMMARY] Maximum Sub-Array (#131)
    ... # sum the integer values of array contents ... algorithm, ... all possible lengths, to check each subarray. ... $ time ruby -r max_sub_array ...
    (comp.lang.ruby)