CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner: Re: [perlfarmer] n Choose k: Edit Log



budman
User

Feb 12, 2012, 8:31 AM


Views: 1351
Re: [perlfarmer] n Choose k

Hi

Thought I might try it out, I came up with a recursion version.


Code
#!/usr/bin/perl 
use strict;

if (scalar(@ARGV) != 2) {
print "Usage: $0 k n\n";
print " K items from set N\n";
exit 1;
}
my ($k,$n) = @ARGV;
my @Set;
push @Set, "e$_" for (1 .. $n);

my @Combos = combine($k,\@Set);
my $i = 0;
printf "%d) %s\n",++$i, "@$_" for @Combos;
print "Total Combinations: ",scalar(@Combos),"\n";

sub combine {
my ($k, $s) = @_;
my $n = scalar(@$s);
my @c = findcombos($k,$n);
my @b;
foreach my $r (@c) {
my @cmb;
push @cmb, $s->[$_] for @$r;
push @b, [ @cmb ];
}
return @b;
}

sub findcombos {
my ($k,$n,$level,$c,$b) = @_;
$level ||= 0;

# initialize arrays
unless (ref($c)){
push @$c, $_ for (0 .. $k-1);
$b = [];
}

my $i = $level;
while ( $i < $n && $c->[$level] < $n ) {
if ( $level + 1 == $k ) {
#print "@$c\n";
push @$b, [ @$c ];
$c->[$level]++;
}
else {
findcombos($k,$n,$level+1,$c,$b);
# advance and reset counters
my $v = $c->[$level] + 1;
$c->[$_] = $v++ for ($level .. $#$c);
}
$i++;
}
return @$b unless $level;
}


I think it may be similar to combine.
I use the arrays to keep track of the levels while processing.

Output:

cmb.pl 4 7
1) e1 e2 e3 e4
2) e1 e2 e3 e5
3) e1 e2 e3 e6
4) e1 e2 e3 e7
....
33) e3 e4 e6 e7
34) e3 e5 e6 e7
35) e4 e5 e6 e7
Total Combinations: 35


Rich


(This post was edited by budman on Feb 12, 2012, 8:39 AM)


Edit Log:
Post edited by budman (User) on Feb 12, 2012, 8:39 AM


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives