Tuesday, April 22, 2008

permutations with repetition




A little Perl snippet that generates all the permutations with repetition allowed, using recursion:


#!/usr/bin/perl
$max_length = 3;
@collection = ('A','B','C');

generate('');

sub generate {
my ($val) = $_[0];
my ($add) = $_[1];
$val .= $add;

my $item;

if (length($val) > $max_length - 1) {
print "$val \n";
} else {
foreach $item (@collection) {
generate($val,$item);
}
}
}


Generates:

AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC