eric256 has asked for the wisdom of the Perl Monks concerning the following question:

Playing with pugs I decided to tackle combinations in a perl6-ish way if i could manage. So I took the binary counting method and applied it. I think the results worked out pretty well but i'm still left betting there is an easier method. What do you think? What could be done different? SVN Version of the code 

sub combinations returns Array  (@list is rw) {
  return () unless @list.elems;
  my @ans;
  for 1 .. 2**@list.elems-1-> $num {
      push @ans, [ @list[ (0 .. sqrt($num)).grep:{ $num +& (2**$_) } ]
+ ];
  }
  return @ans;
} 
my @list = (1..4);
combinations(@list).perl.say;
__OUTPUT__
([1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4]
+, [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4])

[download]

___________
Eric Hodges

Replies are listed 'Best First'.
Re: P6: Combinations Solution
by kvale (Monsignor) on May 20, 2005 at 06:42 UTC
    What you are computing is the power set of a set of elements (minus the empty set), not combinations per se. Here is a p5 solution for comparison: 
    my @check  = qw/ 1 2 3 4/;
foreach my $index (0..2**@check-1) {
   my @combo;
   foreach my $pos (0..@check-1) {
      push @combo, $check[$pos] if  ($index >> $pos) % 2;
   }
   print join " ", @combo, "\n";
}

    [download]

    -Mark

[reply]
[d/l]

      I thought combinations usualy meant all possible (groupings? subsets?) of one or more elements of the original set. "One or more elements selected from a set without regard to the order of selection." -- dictionary.com

      I'm no set theory expert and dictionary.com certainly isn't the be all end all source of mathematicaly truth. So what other definition of combinations do you have AND how would you implement it in perl6 ;)


      ___________
      Eric Hodges
[reply]
        Sorry for the lack of explanation. Combinations has a mathematinal definition more specialized and distinct from the usual dictionary version. Combinations are all the subsets of a set of a given size. So for the set (1,2,3,4) the combination of subsets with 2 elements is ((1,2),(1,3),(1,4),(2,3),(2,4),(3,4). The number of cominations of 4 elements chosen 2 at a time is called "4 choose 2)" or sometimes C(4,2) and in this case is equal to 6.

        If one puts all the subsets generated from 4 choose 0, 4 choose 1, ..., 4 choose 4 into a set, that set of sets is called a power set of the original set.

        I would implement combinations in p5 and then use the mythical p5 to p6 converter :) Just joking, but I haven't dived into p6 yet.

        -Mark

[reply]
Re: P6: Combinations Solution
by revdiablo (Prior) on May 20, 2005 at 16:22 UTC

    As I mentioned in an earlier post, this construct isn't implemented yet in Pugs. Also as I said before, I may be using it incorrectly, but I think this could be implemented using gather/take as follows:

    sub combinations returns Array  (@list is rw) {
  return () unless @list.elems;
  gather {
      for 1 .. 2**@list.elems-1-> $num {
          take [ @list[ (0 .. sqrt($num)).grep:{ $num +& (2**$_) } ] ]
+;
      }
  }
} 
my @list = (1..4);
combinations(@list).perl.say;

    [download]
[reply]
[d/l]

      Actualy it was implemented a few days ago. This post actualy oncovered a small bug where take is flattening the array-ref. Thanks for the input.


      ___________
      Eric Hodges
[reply]

        I saw that gather/take was implemented, but didn't realize there was the flattening bug. Glad my post could help uncover it. I assume there was a test case written and committed already? :-)

[reply]

Back to Seekers of Perl Wisdom