http://www.perlmonks.org?node_id=305294

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Hi monks, I was wondering if you could help ->

I basically need a quick way of creating all possible combinations of 'words' that can be made with 4 letters. I know you can do this with numbers but a unsure about letters.

The words are just any combination of the letters, e.g with 4 letters there is 256 possible conformations.

e.g. with the letters ABCD: words include BADC, BACD, ABDC etc.... cheers

Replies are listed 'Best First'.
Re: creating all possible random 'words' from 4 letters
by Limbic~Region (Chancellor) on Nov 07, 2003 at 14:13 UTC
    Anonymous Monk,
    Algorithm::Loops, written by tye, is fast and efficient. It can properly handle duplicates unlike Algorithm::Permute and it is also pure Perl.
    #!/usr/bin/perl -w use strict; use Algorithm::Loops 'NestedLoops'; my $length= 4; my @chars = ('a' .. 'd'); my $get_combo = NestedLoops([ (\@chars) x $length ]); my @combo; while ( @combo = $get_combo->() ) { print "@combo\n"; }
    Cheers - L~R
Re: creating all possible random 'words' from 4 letters
by QM (Parson) on Nov 07, 2003 at 15:04 UTC
    Tangent Warning

    For those trying to generate all possible 4-letter words [as in all 456,976 of them], glob is your friend:

    #!/your/perl/here use warnings; use strict; use Data::Dumper; my $all_lowercase = '{' . join( ',', 'a'..'z') . '}'; my @x = glob "$all_lowercase" x 4; print "size of \@x = ", scalar @x, "\n"; print Dumper @x; __END__
    Result:
    size of @x = 456976 $VAR1 = 'aaaa'; $VAR2 = 'aaab'; $VAR3 = 'aaac'; $VAR4 = 'aaad'; $VAR5 = 'aaae'; [snip] $VAR456972 = 'zzzv'; $VAR456973 = 'zzzw'; $VAR456974 = 'zzzx'; $VAR456975 = 'zzzy'; $VAR456976 = 'zzzz';

    -QM
    --
    Quantum Mechanics: The dreams stuff is made of

      Using glob is pretty inventive. I like it, except that you generate a really big list*. As long as you're using all 26 letters, the increment operator will give you the list iteratively:
      my $str = 'aaaa'; print $str++, $/ while $str le 'dddd';
      No need to make an array with 26^4 elements!

      OK, using increment is fun, so let's be goofy and do it with just [a-d]:

      my $str = 'aaaa'; while ($str le 'dddd') { print $str++, $/; 1 while $str =~ s/(.)e/chr(1 + ord $1) . 'a'/e; }

      * Update: BrowserUK++ for setting me straight with glob. You learn something new every day here!

      blokhead

        If you don't want them all in one list, just call glob in a scalar context and it will act as an iterator for you.

        perl -le" print while glob '{A,B,C,D}'x4 "

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        Hooray!
        Wanted!

      Or, more simply: my @x = 'aaaa' .. 'zzzz';

      :-)

      -sauoq
      "My two cents aren't worth a dime.";
      
Re: creating all possible random 'words' from 4 letters
by Roger (Parson) on Nov 07, 2003 at 14:14 UTC
    You could have a look at module Algorithm::Permute on CPAN.

    Umm, how wonderful, it even has a sample code to do what you have asked!

    The following code was pulled from CPAN
    use Algorithm::Permute; my $p = new Algorithm::Permute(['a'..'d']); while (@res = $p->next) { print join(", ", @res), "\n"; }
Re: creating all possible random 'words' from 4 letters
by helgi (Hermit) on Nov 07, 2003 at 14:13 UTC
    perldoc -q permute


    --
    Regards,
    Helgi Briem
    hbriem AT simnet DOT is

Re: creating all possible random 'words' from 4 letters
by Elgon (Curate) on Nov 07, 2003 at 14:22 UTC

    Anonymonk,

    I suggest you use the "Search" function at the top left with the keywords "permutations" or "combinations" as this will turn up lots of code to give you a head start. Broadly speaking you want to assign each letter to an index in an array and jumble them up in all possible ways, which is a standard algorithm.

    If you want the maximum number of combinations of four prechosen letters where each letter is only used once, I think that there are 24 combinations btw (4!) and if any letter may be used more than once, there are something like 456,976 combinations (26^4)

    Elgon

    UPDATE: Thanks to pinetree for the link to the maths faq. In the above node, I am talking about permutations and NOT combinations. You live and learn.

    Please, if this node offends you, re-read it. Think for a bit. I am almost certainly not trying to offend you. Remember - Please never take anything I do or say seriously.

Re: creating all possible random 'words' from 4 letters
by pinetree (Scribe) on Nov 07, 2003 at 15:12 UTC

    It looks like you already have some very good suggestions for code to look at. I noticed that some of the responses suggested permutation code and some suggested combination code.

    Before you choose which suggestions to follow up on, you should be clear on what you want - combinations or permutations. See http://mathforum.org/dr.math/faq/faq.comb.perm.html for an explination of the differences.

    Oren
Re: creating all possible random 'words' from 4 letters
by inman (Curate) on Nov 07, 2003 at 15:01 UTC
    There are numerous modules to do permutations. List-Permutor may fit the bill. E.g.

    #! /usr/bin/perl -w use strict; use List::Permutor; my @data = qw / A B C D /; my $perms = new List::Permutor @data; while (my @set = $perms->next) { print "@set\n"; }

    inman

Re: creating all possible random 'words' from 4 letters
by ptkdb (Monk) on Nov 07, 2003 at 14:25 UTC
    Not to nit pick, but...

    Actually for 4 letters A-Z you should get 456976 combinations. With 4 positions, all combinations of 26 letters would be 264

    update: yeah, this dups the above posting, we both got to it at the same time I suppose

Re: creating all possible random 'words' from 4 letters
by Anonymous Monk on Nov 08, 2003 at 00:33 UTC
    Hi monks

    I found this method from John Krahn who posts on some other Perl lists. It takes letters in any order and does the permutations.

    Chris

    #!/usr/bin/perl use strict; use warnings; my @letters = qw /W A C K Y/; my $pairings = 2; for (0..@letters**$pairings-1) { my @combs; do {unshift @combs, $_ % @letters} while $_ = int $_ / @letters; unshift @combs, (0) x ($pairings - @combs); print "@letters[@combs]\n"; }
Re: creating all possible random 'words' from 4 letters
by ysth (Canon) on Nov 07, 2003 at 18:19 UTC
    #!/usr/bin/perl -wl use strict; use warnings; @ARGV = qw/a b c d/ unless @ARGV; print for glob( ("{".join(',',map quotemeta,@ARGV)."}") x @ARGV )
Re: creating all possible random 'words' from 4 letters
by qq (Hermit) on Nov 07, 2003 at 22:33 UTC

    Two easy, not-slick ways:

    perl -e'$a="aaaa";until($a gt"dddd"){print "$a\n" if $a=~/[a-d]{4}/; $ +a++}' perl -e 'for $a ('a'..'d'){for $b ('a'..'d'){for $c ('a'..'d'){for $d +('a'..'d'){print "$a$b$c$d\n"}}}}'
Re: creating all possible random 'words' from 4 letters
by CountZero (Bishop) on Nov 07, 2003 at 23:39 UTC
    How funny, nobody cried "Homework!" yet.

    Are we getting soft?

    CountZero

    "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

Re: creating all possible random 'words' from 4 letters
by Art_XIV (Hermit) on Nov 10, 2003 at 14:26 UTC

    You may want to check out the O'Reilly book Mastering Algorithms in Perl if you can.

    It has a permutation sample and heap of other algorithms that are explained pretty well.

    Hanlon's Razor - "Never attribute to malice that which can be adequately explained by stupidity"