loop in loop method evasion

[motzi]

I need to generate strings consequentially, i do this with that code (length is 3):

@chartab = (0..9, a..z);
foreach $first (@chartab)
 {
  foreach $second (@chartab)
   {
    foreach $third (@chartab)
     {
      print $first, $second, $third, ",";
     }
   } 
 }

Here, depending on the length i remove or add more foreach loop. Well, i need for example a 15-length string generation, need to make 15 loops, its a bit hard work.

Is there any way to make this method more compact?

Thanks.

[ikegami]

Feasibility of ever completing $N=15 aside, the following is simple and uses next to no memory:

use Algorithm::Loops qw( NestedLoops );

my @chartab = (0..9, 'a'..'z');
my $N = 3;
NestedLoops(
    [ (\@chartab) x $N ],
    sub { print @_, ','; },
);

[eye]

Another approach to this is to recognize that your sequence of strings can form a one-to-one map with a sequence of integers. You could then use a single loop and a function to map those integers into your strings.

The trouble is that your task is enormous. You want to generate 36^15 strings. That is well over 2E+23 strings that will require in excess of 1,000,000 exabytes.

Forget the appearance of your code. You have problems if you want this to finish running this year or if you want to save these strings.

[ikegami]

Another approach to this is to recognize that your sequence of strings can form a one-to-one map with a sequence of integers.

The advantage of this method is that it uses no memory.

# XXX Doesn't handle negatives
sub idiv {
    my ($dividend, $divisor) = @_;
    use integer;
    my $quotient  = $dividend / $divisor;
    my $remainder = $dividend - ( $quotient * $divisor );
    return ( $quotient, $remainder );
}

my @chartab = (0..9, 'a'..'z');
my $N = 3;
for (0 .. @chartab**$N-1) {
    my $x = $_;
    for (1..$N) {
        ($x, my $i) = idiv($x, 0+@chartab);
        print $chartab[$i];
    }
    print ',';
}

[motzi]

Well, about 15-character string is only theoretically task, sure i will not use that much, in practice i will only need 5-6 length string max.

[Anonymous Monk]

You actual intent is a little unclear to me. Are you generating permutations with n terms of the list of items in @chartab followed by a comma? If so, recursion would seem the reasonable way to go. Something like (untested):

use strict;
use warnings;

my @chartab = (0..9, 'a'..'z');
my $depth = 4;
print permute(\@chartab,'',$depth);

sub permute {
    my ($chartab_ref, $intro, $depth) = @_;
    return "$intro," if ($depth == 0);

    my $string = q{};
    foreach my $letter (@$chartab_ref) {
        $string .= permute($chartab_ref, $intro.$letter,$depth-1);
    }
    return $string;
}

[ikegami]

While your algorithm does what the OP wants, it is misnamed. It does not return the permutations of the list. The list only contains one zero, yet the output contains strings with multiple zeroes.

[biohisham]

SUGGESTION: Separate your array into different sets, that can make them more manageable, here is a similar discussion Creating tuples based on sets...Cartesian Cross-Product gives a good orientation too...

perhaps you would wanna consider Set::CrossProduct as an OOP approach or read Using Nested Iterators to find a Cross Product...

[bobr]

Or you can use Algorithm::Combinatorics module, specifically variations_with_repetition function. It uses iterator approach, so it consumes quite little memory. As was noted above, the number of results is very large, so following prints just first 50:

use Algorithm::Combinatorics qw(variations_with_repetition);

my $iter = variations_with_repetition([ '0'..'9', 'a'..'z' ], 15);
while($seq = $iter->next) {
    print @$seq,"\n";
    last if ++$count > 50;
}

-- Roman

[bduggan]

You are counting in base 36. So, you can use Math::Base36, e.g.

#!/usr/bin/perl -l

use Math::Base36 qw/encode_base36/;

print lc encode_base36($_,3) for 0..(36**3-1);