Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Random Derangement Of An Array

by jethro (Monsignor)
on Jul 05, 2008 at 21:50 UTC ( #695755=note: print w/replies, xml ) Need Help??


in reply to Random Derangement Of An Array

for my $i (1..$#a) { my $random= rand( $i); swap(\$a[$i], \$a[$random]); }
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

Replies are listed 'Best First'.
Re^2: Random Derangement Of An Array
by Joost (Canon) on Jul 05, 2008 at 22:03 UTC
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

      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://695755]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (2)
As of 2021-02-28 03:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?