Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Character Combinations

by viGuy (Initiate)
on Aug 22, 2003 at 21:46 UTC ( #285933=perlquestion: print w/replies, xml ) Need Help??
viGuy has asked for the wisdom of the Perl Monks concerning the following question:

First off - if you feel the question is un-ethical - fair enough - I am inclined to agree, but this is still an interesting question to which perl I belive is ideally suited - so, disclaimer aside, here is what I would like to achieve:

What would be the most efficient way to produce every possible combination of a given set of charactors in a string?

Here are my thoughts so far: Using hashes - I belive these to be more efficient than arrays - one hash assigned to each charactor in the string. The hash would contain the possible charactor values with incremental numbers for the key values.
E.G: For the first charactor in the string I would have a hash of: key-value,A-1,B-2,C-3
for the second charactor in the string I would have a hash of: a-1,b-2,c-3
So for the first iteration I would call hash1{key1} hash2{key1} for the second iteration I would call hash1{key2} hash2{key1} etc

Now you know and I know how this could be applied - but there are plenty of "off the site" products out there that I could use to achieve the same thing. This is more for 'fun' to figure out how to do this EFFICIENTLY in perl. So - what do you think? How would you approach this?

20030823 Edit by jeffa: Changed title from 'Charactor Combinations '

Replies are listed 'Best First'.
Re: Character Combinations
by Limbic~Region (Chancellor) on Aug 22, 2003 at 22:02 UTC
    I don't see this as un-ethical, but if the purpose is to provide a brute force crack against passwords - it is probably pretty silly. For instance - take a look at this thread for some numbers. If this is your goal, you would be much better off using a C compiled based program design for that effort. Even that is not un-ethical if the purpose is to ensure the integrity of the passwords of a given system you are responsible for the security of and you have ensured that it is legal. Since you didn't ask for that, I won't point you in the right direction.

    Do you have something else in mind?

    Cheers - L~R

    Update: I was looking for an iterative solution an tye recommended Algorithm::Loops. Even though he hasn't uploaded it yet, the source is available here. My original sentiment stands, but this is how I would do it if I could think of a legitimate reason to do it.

    On my Mom's mediocre computer, this would take 555 years to complete - give or take a few months :-)

Re: Character Combinations
by graff (Chancellor) on Aug 22, 2003 at 22:44 UTC
    You didn't mention how long the string is supposed to be or how many characters are possible at each position in the string; obviously these points would have an impact on the practicality of the process.

    In any case, I think you're mistaken about preferring the use of hashes. Unless I misunderstood your post, the app you're talking about is just a matter of nested loops, one loop for each character position in the string. The inner-most loop prints the concatenation of all the loop iterators. The number of iterations on each loop is simply the number of possible characters to use at the corresponding position. It could be structured recursively to support handling strings of various lengths. But using hashes would be a waste of time, and a vast waste of memory.

Re: Character Combinations
by antirice (Priest) on Aug 23, 2003 at 01:33 UTC

    And now for my attempt to reinvent this wheel:

    my @alpha = ('a'..'c'); my @counter = (); sub get_next { for (@counter) { $_++; last if ($_ <= $#alpha); $_ = 0; } push @counter,0 unless grep($_>0,@counter); return join"",map($alpha[$_],@counter); } for ($_ = get_next();4 > @counter ;$_ = get_next()) { print "$_ "; } __DATA__ output: a b c aa ba ca ab bb cb ac bc cc aaa baa caa aba bba cba aca b +ca cca aab bab cab abb bbb cbb acb bcb ccb aac bac cac abc bbc cbc ac +c bcc ccc

    Of course, maybe it was a silly try. But still, I like it :)

    Hope this helps.

    The first rule of Perl club is - use Perl
    ith rule of Perl club is - follow rule i - 1 for i > 1

Re: Character Combinations
by esh (Pilgrim) on Aug 23, 2003 at 06:53 UTC

    if you just want the 3 letter combinations of the 26 lowercase letters in the English alphabet, this is pretty simple and probably very fast:

    #!/usr/bin/perl -w use strict; my $size = 3; # number of characters in the target string. my $string = 'a' x $size; my $end = 'z' x $size; do { print $string++, "\n"; } while $string ne $end;

    This would also work for uppercase, but as soon as you want to mix cases, add numbers, and add punctuation it falls short as a solution.

    The mechanism used here is the automagical increment operator (++) which does cool stuff when applied to a string starting with a letter and consisting of letters and numbers.

    Update: If you want to start with 1 character strings and go up to N characters, just change the initialization to:

    my $string = 'a';
    -- Eric Hammond
Re: Character Combinations
by viGuy (Initiate) on Aug 22, 2003 at 21:51 UTC
    Arrrg - I always spot my mistakes once I have posted, anyway - spelling aside:
    should be
Re: Character Combinations
by chunlou (Curate) on Aug 22, 2003 at 23:00 UTC
      Permutations are not combinations. For instance - say I wanted to find all combinations of 4 character strings with each position able to be 26 different letters. This is what I believe is being asked for. I am pretty sure there is an iterative solution - but all I can come up with right now are recursive ones.

      Cheers - L~R

        You mean this?
        use Algorithm::FastPermute; my @c = ('a'..'c'); for my $i (0..2) { for my $j (0..2) { my @c = @c[$i..$j] if $i <= $j; permute {print @c , "\n"} @c; } } __END__ a ab ba abc acb cab bac bca cba b bc cb c

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://285933]
Approved by graff
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (15)
As of 2017-03-27 21:43 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (324 votes). Check out past polls.