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

Finding all sets of chars

by Anonymous Monk
on Oct 29, 2005 at 20:21 UTC ( #503904=perlquestion: print w/replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I tried to Google this but I wasn't really sure what to search for.

I want to setup a script that finds ALL combinations of a set number of characters. For instance, if it was 1 character it would find all the single numbers and digits. If I asked for two digits, it'd spit out aa,ab,ac.. 10,11,12,1a,1b..... until all combinations are found.

This seems rather complicated but probably something that a module was already created to do. I do need to be able to specify which charaters: numbers, letters, special characters like asterics, etc that should be used.

Is there such a module or anyone know of what to search for or have a solution?

Replies are listed 'Best First'.
Re: Finding all sets of chars
by Zaxo (Archbishop) on Oct 29, 2005 at 20:50 UTC

    The glob builtin can do what you want.

    my @digits = '0'..'9'; my @caps = 'A'..'Z'; my @lower = 'a'..'z'; my @alnum = (@digits, @caps, @lower); # glob patterns my $digits = do {local $" = ','; "{@digits}"}; my $caps = do {local $" = ','; "{@caps}"}; my $lower = do {local $" = ','; "{@lower}"}; my $alnum = do {local $" = ','; "{@alnum}"}; print "@{[glob $lower . $digits]}\n"; __END__ a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 c0 c1 c2 c +3 c4 c5 c6 c7 c8 c9 d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 e0 e1 e2 e3 e4 e5 e +6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 g0 g1 g2 g3 g4 g5 g6 g7 g8 g +9 h0 h1 h2 h3 h4 h5 h6 h7 h8 h9 i0 i1 i2 i3 i4 i5 i6 i7 i8 i9 j0 j1 j +2 j3 j4 j5 j6 j7 j8 j9 k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 l0 l1 l2 l3 l4 l +5 l6 l7 l8 l9 m0 m1 m2 m3 m4 m5 m6 m7 m8 m9 n0 n1 n2 n3 n4 n5 n6 n7 n +8 n9 o0 o1 o2 o3 o4 o5 o6 o7 o8 o9 p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 q0 q +1 q2 q3 q4 q5 q6 q7 q8 q9 r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 s0 s1 s2 s3 s +4 s5 s6 s7 s8 s9 t0 t1 t2 t3 t4 t5 t6 t7 t8 t9 u0 u1 u2 u3 u4 u5 u6 u +7 u8 u9 v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 w0 w1 w2 w3 w4 w5 w6 w7 w8 w9 x +0 x1 x2 x3 x4 x5 x6 x7 x8 x9 y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 z0 z1 z2 z +3 z4 z5 z6 z7 z8 z9
    Clearly, the number of elements in the solution grows rapidly with the number of characters in the set and in the string.

    A shortcut for a glob pattern for $num of the same type is: my $pat = $type x $num; using the x replicator op.

    Added: Limbic~Region points out that my example isn't the one you used. That was intentional, for brevity of the result. The pattern for your two-character example is my $two_char = $alnum x 2;. It results in 3844 distinct combinations.

    After Compline,

Re: Finding all sets of chars
by Limbic~Region (Chancellor) on Oct 29, 2005 at 20:45 UTC
    Anonymous Monk,
    There are plenty of modules on CPAN that will do this for you. There are also many examples of home grown code here you could have found using Super Search.

    Are you sure you want combinations? There is a difference between combinations and permutations and you also need to consider replacement and duplicates. I think the following code, adapted from How To: Make An Iterator does what you want.

    #!/usr/bin/perl use strict; use warnings; # Change this as desired my $size = 2; my $next_perm = fix_size_perm($size, 'a'..'z', 0..9); while ( my $perm = $next_perm->() ) { print "$perm\n"; } sub fix_size_perm { my ($size, @list) = @_; my @curr = (0) x ($size - 1); push @curr, -1; return sub { if ( (join '', map { $list[ $_ ] } @curr) eq $list[ -1 ] x @cu +rr ) { @curr = (0) x (@curr + 1); } else { my $pos = @curr; while ( --$pos > -1 ) { ++$curr[ $pos ], last if $curr[ $pos ] < $#list; $curr[ $pos ] = 0; } } return undef if @curr > $size; return join '', map { $list[ $_ ] } @curr; }; }

    Cheers - L~R

    Update: Changed code example to hopefully better fit the problem.

Re: Finding all sets of chars
by blokhead (Monsignor) on Oct 29, 2005 at 21:21 UTC
    The number of such strings grows exponentially as you increase the desired length (which can out of hand really fast). To prevent from having to keep all of the strings in memory at once, you can use an iterator to give you just one item at a time. Even though the glob function can be used like an iterator, it still internally keeps all of the items in memory at once, so there is no memory gain by using glob to iterate. Here's a simple iterative solution using NestedLoops from Algorithm::Loops:
    use Algorithm::Loops 'NestedLoops'; my @chars = ( 'a' .. 'z', 1 .. 9 ); my $len = 3; NestedLoops( [ (\@chars) x $len ], sub { my $str = join "", @_; ## do something with $str } );


Re: Finding all sets of chars
by chas (Priest) on Oct 29, 2005 at 20:57 UTC
    You could do something like:
    @a= glob "{a,b,c,d,e,1,2,3,4,5}"x 2; for(@a){print "$_ "}

    (but using the full set of characters and numbers that you want and varying the multiplier. And I guess you mean permutations.)
    (Oh, zaxo posted the same idea, more detail, while I was typing...)
Re: Finding all sets of chars
by eyepopslikeamosquito (Chancellor) on Oct 29, 2005 at 21:05 UTC

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://503904]
Approved by Errto
[Corion]: Hi Abhay_Anand!

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (2)
As of 2017-08-17 07:19 GMT
Find Nodes?
    Voting Booth?
    Who is your favorite scientist and why?

    Results (282 votes). Check out past polls.