in reply to Re: Random Derangement Of An Array
in thread Random Derangement Of An Array
Shuffle the numbers 1..$#list. Add in the number 0 (just on the end). Then break this list up into 1 or more substrings of at least 2 indices each. Rotate the items at the indices of each substring.
Breaking the list up into pairs (as you did above) is one way to do that if the number of items is even. Perhaps better is to just keep it one list and rotate the whole list, as demonstrated at Re: Derangements iterator.
If you remove the "at least 2 indices each" requirement then rotating gives you permutations, not derangements. Of course, not all derangements (nor permutations) are equally likely when using this technique. But it does select from the subset of derangements that are random rotations uniformly.
Which method is more appropriate depends on the X of your XY problem (which you didn't specify, of course).
 tye


Replies are listed 'Best First'.  

Re^3: Random Derangement Of An Array (rotate)
by Limbic~Region (Chancellor) on Jul 05, 2008 at 22:56 UTC  
by moritz (Cardinal) on Jul 09, 2008 at 18:36 UTC  
by Limbic~Region (Chancellor) on Jul 09, 2008 at 21:58 UTC 