|Perl: the Markov chain saw|
Re: Is there a way more easy?by martin (Pilgrim)
|on Jun 21, 2012 at 12:46 UTC||Need Help??|
While variations_with_repetition and mapm can reproduce the behaviour of the OP's original code, I wonder if his actual intent was precisely that.
Note that including the empty string in the list of "characters" adds shorter words to the output, while also introducing repetition and breaking lexicographic order. Each 5-letter word will appear 6 times, each 4-letter word 15 times, each 3-letter word 20 times, each 2-letter word 15 times, each single-letter word 6 times, and an empty line will also be in the output. Repeated strings will comprise 8.89 percent out of a total of 24,794,911,296 lines of output.
Let us assume that we wanted to generate all distinct non-empty strings with a given maximum length that can be build from a given alphabet.
The OP's approach with nested loops is in fact suitable for this task, with a little bit of modification.
The variable @alphabet defines the characters available and their order. It does not contain an empty string. If we wanted another minimum word length we could simply remove the print statements in some of the outer loops.
The downside of this approach is that the word lengths are not controlled by simple parameters and that the code gets more and more repetitive with greater lengths.
A possible solution would be to put all those loop variables in an array and simulate how the nested loops iterate through those variables with a single loop, though at the price of a more complicated increment part, like this:
I recommend using a much smaller alphabet to test this. Note that I chose to use integer numbers in the @state array serving both as counters and indexes into the alphabet. The characters to print are then taken from an array slice.
While the second algorithm is certainly not easier to understand than the first, if a little bit shorter, it is much more flexible and still memory-efficient.
For a deeper understanding of combinatorial algorithms I warmly recommend the modern classic work by Donald E. Knuth, and its upcoming sequel.