CGI/Perl Guide | Learning Center | Forums | Advertise | Login Site Search: in Perl Guide PerlGuru Forums Learning Ctr
 MAIN INDEX SEARCHPOSTS WHO'S ONLINE LOG IN

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

budman
User

Feb 12, 2012, 8:31 AM

Views: 2640
 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 this forum this category all forums for All words Any words Whole Phrase (options) Powered by Gossamer Forum v.1.2.0