Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Random Derangement Of An Array

by Limbic~Region (Chancellor)
on Jul 05, 2008 at 21:47 UTC ( #695754=note: print w/replies, xml ) Need Help??


in reply to Random Derangement Of An Array

All,
Here is an idea I came up with in #perl (freenode) thanks to a few folks there. Assume an even number of elements:
  • 1. Shuffle the indices of the array (copy not actual values)
  • 2. Swap adjacent pairs (actually change values)

For instance: 0 - 9 might become 5, 3, 1, 2, 4, 7, 9, 8, 0, 6
Swap index 5 with 3, 1 with 2, 4 with 7, and 9 with 8

Cheers - L~R

Replies are listed 'Best First'.
Re^2: Random Derangement Of An Array (rotate)
by tye (Sage) on Jul 05, 2008 at 22:11 UTC

    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        

      tye,
      Which method is more appropriate depends on the X of your XY problem (which you didn't specify, of course).

      I am writing a game for a relative to generate cryptograms. Anything not too obvious would be "good enough".

      On the other hand, I am interested in more than just "good enough" solutions for the pure pursuit of knowledge.

      Cheers - L~R

        I am writing a game for a relative to generate cryptograms.

        Use List::Util::shuffle for the key generation. It's not bad to map letters in the clear text to the same letter in the cypher text - as long as it's not more often than the statistical average.

        Actually the Enigma forbade that, which was one of the reasons why it could be broken during the second world war.

        BTW a common scheme for generating a key was to take a word, remove all duplicate characters, and fill the rest of the alphabet from the back:

        key: LimbicRegion removed duplicates: limbcregon filled with the rest of the alphabet: limbcregonzyxwvutsrqpkjhfdcba

        But that's not very secure, and mostly of historical interest ;-)

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2021-03-03 12:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favorite kind of desktop background is:











    Results (77 votes). Check out past polls.

    Notices?