Re: random sorting a collection

[Peter Duniho]

On Wed, 28 May 2008 06:23:35 -0700, Adam Sandler <co****@excite.comwrote:

[...]
The problem is, the sorted array can now contain duplicates!

No, it can't. Not unless it had duplicates to start with.

Personally, I wouldn't bother with such a contrived loop. Something
simpler is fine:

for (int i = 0; i < a.Length; i++)
{
int j = r.Next(a.Length);
String temp = a[i];

a[i] = a[j];
a[j] = temp;
}

Then you avoid all the -1 and +1 and off-by-one. For the purposes of
shuffling the input, it doesn't matter that you might shuffle an item that
you'd already shuffled. It's still random.

That whole thread you referenced is a bit sketchy, if you ask me.

Pete

[Jon Skeet [C# MVP]]

On May 28, 3:39 pm, "Peter Duniho" <[e-mail]>
wrote:

<snip>

Then you avoid all the -1 and +1 and off-by-one. For the purposes of
shuffling the input, it doesn't matter that you might shuffle an item that
you'd already shuffled. It's still random.

It ends up being less random though. It's less likely that something
will end up in its initial position than with a true shuffle, IIRC. It
takes a *little* more work to get rid of the off-by-one errors, but
it's not that bad.

I'd personally write it as:

// i=position we're going to replace (possibly with same element)
// Everything less than i is already shuffled
for (int i=0; i < a.Length; i++)
{
// target is in range [i, a.Length)
int target = i+rng.Next(a.Length-i);

String temp = a[i];
a[i] = a[target];
a[target] = temp;
}

Jon

[Peter Duniho]

On Wed, 28 May 2008 08:30:18 -0700, Jon Skeet [C# MVP] <sk***@pobox.com>
wrote:

On May 28, 3:39 pm, "Peter Duniho" <[e-mail]>
wrote:

<snip>

>Then you avoid all the -1 and +1 and off-by-one. For the purposes of
shuffling the input, it doesn't matter that you might shuffle an item
that
you'd already shuffled. It's still random.

It ends up being less random though. It's less likely that something
will end up in its initial position than with a true shuffle, IIRC.

By the way, I did finally get a chance to try to look up a reference that
would refute or verify this. I found in Wikipedia an argument that points
out that for a shuffle, there are N! permutations, but that selecting a
random swap from every possible index on each iteration produces N^N
possible outcomes for the random selections. It then points out that N^N
is never divisible by N! and uses that to claim that some permutations
must occur more often (basically, there are duplicates in the possible
random outcomes, but only for some permutations).

Anyway, that's a long way of saying I think you're right.

As long as I'm commenting, I'll point out though that if we're going to
fix the algorithm so that it produces correct uniform distribution, we
might as well take advantage of the chance and reduce our iteration count
by one. So instead of:

for (int i = 0; i < a.Length; i++)

we can have:

for (int i = 0; i < a.Length - 1; i++)

Not nearly as good a nitpick as the one you came up with, but it's all
I've got. :)

There's another optimization with respect to not swapping with something
winds up in the same place, but that involves a much more (relatively
speaking) complex change to the basic algorithm, and so more easily
qualifies as a premature optimization. The above I think makes sense due
to its simplicity, even as I would ignore the potentially more beneficial
optimization. I find this whole thought process somewhat
counter-intuitive and ironic. :)

Pete