http://qs321.pair.com?node_id=695760

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

• Comment on Re^2: Random Derangement Of An Array (rotate)

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
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