combinatorics, scripts for

[Harald Weber]

Hi !

There is no CPAN module that covers
the basics of combinatorics, is there ? (gurus: yawn!)

There are some modules for permutation (k=n),
but this is only a very special case to combine
a set of items.

Below you can find four scripts(comb1,comb2,comb3,comb4)
suited for the common combinatorial tasks.

Basically, there are 4 possibilities to choose k items
out of a set of n items ( well, that¹s what I have read .

Let¹s say k=3; n=(a,b,c,d)

1. no repetition, no order (k,n > 0; k <= n)

abc, abd, acd, bcd (4)

2. no repetition, order (k,n > 0; k <= n)

abc,abd,acb ... dcb (24)

3. repetition, no order (k,n > 0)

aaa,aab,aac,aad,abb ... ddd (20)

4. repetition, order (k,n > 0)

aaa,aab,aac,aad,aba ... ddd (64)

Now, there should be four algorithms spitting out the
desired combinations without restricting the users choice
of k and n.

On command line it could look like this:

combx length item1 item2 ..., e.g.

combx 3 a b c d or
combx 6 cherry coconut orange banana peach

Maybe you¹d like to work out better solutions.
I¹m sure it¹s easy for you to write more stylish code,
but it shouldn¹t be much slower than this one.
Hopefully this posting is somehow helpful
(give me a hint: is this too much code for a posting ?!).

Harald


+++++

#!/usr/bin/perl -w
#Program comb1 (combinatorics: repeat - ,order -)
#Usage: comb1 length item1 item2 ...

use strict;

my ($length,@items) = @ARGV;
my $code = "my \$x0 = -1;\n";

for (my $c=1; $c <= $length; $c++){
$code .= "for (my \$x$c = \$x" . ($c-1)
. " + 1; \$x$c <= \$#items - \$length + $c; \$x$c++){\n"
}

$code .= 'print "';

for (my $c=1; $c <= $length; $c++)
{$code .= "\$items[\$x$c] "}

$code .= '\n"' . '}' x$length . "\n";

eval($code);

#print $code

+++++

#!/usr/bin/perl -w
#Program comb2 (combinatorics: repeat - , order +)
#Usage: comb2 length item1 item2 ...

use strict;

my ($length,@items) = @ARGV;
my @x0 = \(@items);
my $code = "";


for (my $c=1; $c <= $length; $c++){
$code .= "for (my \$x$c = 0; \$x$c <= \$#x" . ($c-1) . "; \$x$c++)"
. "{my \@x$c = \@x" . ($c-1) . "; splice(\@x$c,\$x$c,1);\n"
}

$code .= 'print "';

for (my $c=0; $c <= $length - 1; $c++)
{$code .= "\${\$x" . $c . "[\$x" . ($c+1) . "]} "}

$code .= '\n"' . '}' x$length . "\n";

eval($code);

#print $code

+++++

#!/usr/bin/perl -w
#Program comb3 (combinatorics: repeat +, order -)
#Usage: comb3 length item1 item2 ...

use strict;

my ($length,@items) = @ARGV;
my $code = "my \$x0 = 0;\n";

for (my $c=1; $c <= $length; $c++){
$code .= "for (my \$x$c = \$x" . ($c-1)
. "; \$x$c <= \$#items; \$x$c++){\n"
}

$code .= 'print "';

for (my $c=1; $c <= $length; $c++)
{$code .= "\$items[\$x$c] "}

$code .= '\n"' . '}' x$length . "\n";

eval($code);

#print $code

+++++

#!/usr/bin/perl -w
#Program comb4 (combinatorics: repeat +, order +)
#Usage: comb4 length item1 item2 ...

use strict;

my ($length,@items) = @ARGV;
my $code = "";

for (my $c = 1; $c <= $length; $c++){
$code .= "for (my \$x$c = 0; \$x$c <= $#items; \$x$c++)\n{"
}

$code .= 'print "';

for (my $c=1; $c <= $length; $c++)
{$code .= "\$items[\$x$c] "}

$code .= '\n"' . '}' x$length . "\n";

eval($code);

#print $code

+++++

 

[Chris Charley]

Hi !
[snip]

Maybe you¹d like to work out better solutions.
I¹m sure it¹s easy for you to write more stylish code,
but it shouldn¹t be much slower than this one.
Hopefully this posting is somehow helpful
(give me a hint: is this too much code for a posting ?!).

Harald

Hi Harald,

Just a suggestion! I hope I am correct when I say that to have more
useful functions, a good programmer in general will return a array of
numbers, a string or an array of strings. That way, if you only want
to print the results of the permutation method used, you can just
iterate over the returned array - same if you want to do any sort of
manipulation. But when the print operator is inside the function,
thats the only operation being performed. In other words, in this
case, to return an array of all permutations is more flexible. I
learned this point from M-J. Dominus's web site -
http://perl.plover.com/.

HTH