Re: Random Derangement Of An Array

for my $i (1..$#a) {
  my $random= rand( $i);
  swap(\$a[$i], \$a[$random]);
}
[download]

Since any position is only swapped once with any of the previous places, there can't be the initial value in any place. But still any value can go to any other position in the array. Per induction I think I can show that the values are equally distributed.

EDIT: Thanks Joost, I was too sloppy, even used { instead of [. If I remember correctly it would work without the \ since @_ in the sub is an alias to the parameters, but this way the side effect is more obvious

Comment on Re: Random Derangement Of An Array Download Code

Replies are listed 'Best First'.
Re^2: Random Derangement Of An Array by Joost (Canon) on Jul 05, 2008 at 22:03 UTC
I think you meant `swap(\$a[$i], \$a[$random]);` [download] Which looks like it may work. But randomness always got me confused (and into furious rows with my math teacher, but that's another story). "What should it profit a man, if he should win a flame war, yet lose his cool?"	[reply] [d/l]
Re^2: Random Derangement Of An Array by blokhead (Monsignor) on Jul 06, 2008 at 11:05 UTC
I'm skeptical about this one. It's nice, but it can only give factorial(n-1) possible outputs, since that is the number of choices made in the algorithm. But there are many more derangements than that -- the number is essentially factorial(n)/e, which is larger if n>2. So I don't think it gets the entire range of derangements. For instance, I think one that it wouldn't be able to get is: (4,3,2,1). In the last step, you must swap the 4 into its final position, so the 4 would have to be swapped with the 1 in the first position. But the 1 would definitely no longer be in the first position at that time. blokhead	[reply]
Re^3: Random Derangement Of An Array by jethro (Monsignor) on Jul 06, 2008 at 12:46 UTC
Excellent example. So that algorithm is sadly lacking, and my proof has a hole as well. That happens when you try to proove something in your head instead of really doing the math.	[reply]


Think about Loose Coupling
	PerlMonks