in reply to quick and dirty cryptogram puzzle

Thanks!++ I enjoy the occasional cryptogram puzzle, and I'm always glad to find a good example of using a GUI library other than Tk, so I was really happy to see this.

There's just one thing about your "gen_random_key" function (update: as it was originally posted, without the "derangement" part), and it's an issue I had thought of posting here at the Monastery under SoPW. In every published cryptogram puzzle I've ever seen (i.e. in newspapers and puzzle books), the shuffling of the substitution cipher is always "complete", in the sense that no letter is ever "substituted" with itself. Unfortunately, your gen_random_key function does not have this property.

It's not clear to me whether your algorithm for shuffling differs in method from the "standard" shuffle (e.g. as provided in List::Util), but having looked at the results of both approaches, they seem to produce the same quality of output with regard to "completeness" of the shuffle: as often as not, one or more of the "substitution" pairs end up with the same letter as both "clear text" and "cipher" (e.g. "B is replaced by B").

So, being rather rusty with sorting and shuffling algorithms, I'm wondering: what would be a "good" method for doing a complete shuffle (where "good" means "efficient", and/or "not requiring an indeterminate number of iterations"). For example, the following "complete_shuffle" function will never return anything other than a completely shuffled list, but the problem is it may try hundreds of random numbers before finishing a list of 26 items, and for reasons I have not yet figured out, sometimes it simply does not return at all... 

sub complete_shuffle
{
    my @sorted = @_;
    my @shuffled = ();
    my $niters = 0;
    my %shuff_used = ();
    for my $i ( 0 .. $#sorted ) {
        my $j = $i;
        while ( $j == $i or exists( $shuff_used{$j} )) {
            $j = int(rand(@sorted));
            $niters++;
        }
        $shuffled[$j] = $sorted[$i];
        $shuff_used{$j}++;
    }
    warn "complete shuffle finished in $niters iterations\n";
    return @shuffled;
}

[download]
I suspect there are good reasons for solving the "complete shuffle" problem (besides wanting to do cryptogram puzzles), so I'd like to know how to solve it properly.

Replies are listed 'Best First'.
Re^2: quick and dirty cryptogram puzzle (derangement)
by tye (Sage) on Jan 01, 2008 at 18:18 UTC
[reply]
      Aha! Thanks. This is a perfect demonstration of the fundamental problem for search-engine users: of course there would be a "jargon term" that designates exactly the particular concept you have in mind -- but when you don't know that term, searches based on various descriptions of (circumlocutions about) the concept tend to have very low precision (and recall success for such queries can be no better than a crap-shoot). There's no substitute for relevant experience...
[reply]

        FYI, I couldn't remember the term so I went to [mathworld://Permutation.html] (Permutation.html). At the bottom are links to "Complete Permutation" and to "Derangement" (clicking the first simply gives a page that points to the second). I've used similar methods to find technical terms for mathematical concepts before; mathematical concepts often have names that are not distinctive so searching for them even when you know them can be problematic. The high degree of cross-linking at MathWorld is one of my favorite features of the site.

        - tye        

[reply]
[d/l]
Re^2: quick and dirty cryptogram puzzle
by Snarius (Sexton) on Jan 01, 2008 at 19:59 UTC
    Thanks for the criticism! I've not played many cryptograms, so I wasn't familiar with that idea. I wouldn't have called it a "complete shuffle" though. An "incomplete shuffle", maybe :)

    I've added a bit to my shuffling function to ensure a derangement. It's a bit quick and dirty... 
    sub gen_random_key{
    ####sub fisher_yates_shuffle {
    my @array = split ("", $alpha);
    my @alpha = @array;
    for (my $i = @array; --$i; ) {
        my $j = int rand ($i+1);
        next if $i == $j;
        @array[$i, $j] = @array[$j, $i];
    }
    for (0..$#alpha){
        $decrypt{$alpha[$_]} = $array[$_];
        $encrypt{$array[$_]} = $alpha[$_];
    }
    #ensure a derangement
    for (0..$#alpha){
        if ($alpha[$_] eq $array[$_]) {
            gen_random_key();
            #warn 'key not deranged, setting another..';
            return;
        }
    }
}

    [download]
[reply]
[d/l]
      next if $i == $j;

      [download]
      This line is unnecessary. It's been discussed before here and elsewhere, but in an array of any significant size (>10 or 20 or so), the odds that i and j are equal are low enough that the logic to test if they are equal outweighs the cost of just swapping the array element with itself (i.e. you're testing to see if they're equal on every iteration, costing something on every iteration, where if you dont' test you'd hardly ever be swapping something with itself anyway).
[reply]
[d/l]

In Section Code Catacombs