Re: Randomly outputting an array

Arthur J. O'Dwyer wrote:
On Sun, 16 Jul 2006, Logan Shaw wrote:
Ico wrote:
Ico <usenet@xxxxxxx> wrote:

Is N times swapping two elements considered enough to truly 'randomize'
an array ?

That was a stupid question, please ignore me...

Actually, it's not a stupid question. It's a very good question.
The answer is definitely "no".

No, the answer is "it depends."

My knee-jerk reaction was also "no", but then I realized that Ico was
replying to Richard Heathfield's post, which is an obvious "yes" (or
should be, if he didn't make any unnecessary mistakes).

I guess it depends on whether the question is

1. "Is it really possible that there are correct algorithms for
randomizing an array that can accomplish it with as little
as N swaps of two elements?"
or
2. "Is it true that merely swapping two elements N times will
guarantee correct randomization of the array?"

I was interpreting the question as #2, but it might've been meant
as #1.

Picking N pairs uniformly at random and swapping them will definitely
not shuffle the array, since there are (N^2)^N = N^(2N) ways to pick
N pairs, and N! ways to shuffle the array, and N^(2N) is generally not
a multiple of N!.

Yeah, but more than that, even visiting every single element of the
array isn't necessarily correct. Here's an algorithm that looks at
first like it might be good for shuffling an array:

int a[N] = { ... some stuff ... };

for (int i = 0; i < N; i++)
{
j = random_in_range_inclusive (i+1, N-1);
swap (& a[i], & a[j]);
}

At first glance, that algorithm has some good characteristics. It
visits every element in the array, so there is no way it will leave
an element untouched accidentally. It puts every element into a
random position, so everything gets moved. But it's not correct.

You can show that it's incorrect quite easily: it will always take
the first element in the array and put it somewhere other than the
first position. But here's the kicker for this particular algorithm:
any algorithm which correctly randomly shuffles an array of length N
will have a probability of 1/(N!) of giving you back exactly the same
ordering you started with. After all, the ordering you started with
is one of the N! possible orderings, so it should be represented with
a probability equal to all the other orderings. But the above code
always moves the first element somewhere else, so it gives you a zero
probability of giving you back your original order; therefore, it's
not a correct algorithm.

Anyway, the point was just that there are lots of ways for this to
go wrong if you don't understand what you're really after, namely
choosing one of the N! possible orderings at random and with equal
probability as any of the others.

- Logan
.

Relevant Pages

  • 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)
  • Re: counting subsets of S so that sum(S_n) = N
    ... and make my algorithm generate only unique subsets? ... and the array of boolean at one step of the algorithm is ... implementation without needing recursion. ... subsequence in W, process it and return. ...
    (comp.programming)