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.

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.