Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^2: Random Derangement Of An Array

by blokhead (Monsignor)
on Jul 06, 2008 at 11:05 UTC ( #695806=note: print w/ replies, xml ) Need Help??


in reply to Re: Random Derangement Of An Array
in thread Random Derangement Of An Array

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


Comment on Re^2: Random Derangement Of An Array
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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (17)
As of 2015-07-02 18:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (44 votes), past polls