How can I generate all subsets of a list in Perl?

Question

I have a mathematical set in a Perl array: (1, 2, 3). I'd like to find all the subsets of that set: (1), (2), (3), (1,2), (1,3), (2,3).

With 3 elements this isn't too difficult but if set has 10 elements this gets tricky.

Thoughts?

Answer 1

See Data::PowerSet, http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html , etc.

Answer 2

You can use Data::PowerSet like Matthew mentioned. However, if, as indicated in your example, you only want proper subsets and not every subset, you need to do a little bit more work.

  # result: all subsets, except {68, 22, 43}.
  my $values = Data::PowerSet->new({max => 2}, 68, 22, 43);

Likewise, if you want to omit the null set, just add the min parameter:

  # result: all subsets, except {} and {68, 22, 43}.
  my $values = Data::PowerSet->new({min => 1, max => 2}, 68, 22, 43);

Otherwise, to get all subsets, just omit both parameters:

  # result: every subset.
  my $values = Data::PowerSet->new(68, 22, 43);

Answer 3

Use Algorithm::ChooseSubsets.

Answer 4

Since you say "mathematical set", I assume you mean there are no duplicates.

A naive implementation that works for up to 32 elements:

my $set = [1,2,3];
my @subsets;
for my $count ( 1..(1<<@$set)-2 ) {
    push @subsets, [ map $count & (1<<$_) ? $set->[$_] : (), 0..$#$set ];
}

(For the full range of subsets, loop from 0 to (1<<@$set)-1; excluding 0 excludes the null set, excluding (1<<@$set)-1 excludes the original set.)

Update: I'm not advocating this over using a module, just suggesting it in case you are looking to understand how to go about such a problem. In general, each element is either included or excluded from any given subset. You want to pick an element and generate first all possible subsets of the other elements not including your picked element and then all possible subsets of the other elements including your picked element. Recursively apply this to the "generate all possible subsets". Finally, discard the null subset and the non-proper subset. In the above code, each element is assigned a bit. First all subsets are generated with the high bit on, then all those with it off. For each of those alternatives, subsets are generated first with the next-to-highest bit off, then on. Continuing this until you are just working on the lowest bit, what you end up with is all the possible numbers, in order.

Answer 5

If you don't want to use an existing module or can't then you can simply code your own subset generation algorithm using a bit-mask and a binary counter. Sample code follows -

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

my @set     = (1, 2, 3);
my @bitMask = (0, 0, 0); #Same size as @set, initially filled with zeroes

printSubset(\@bitMask, \@set) while ( genMask(\@bitMask, \@set) );

sub printSubset {
  my ($bitMask, $set) = @_;

  for (0 .. @$bitMask-1) {
    print "$set->[$_]" if $bitMask->[$_] == 1;
  }
  print"\n";

}

sub genMask {
  my ($bitMask, $set) = @_;

  my $i;
  for ($i = 0; $i < @$set && $bitMask->[$i]; $i++) {
    $bitMask->[$i] = 0;
  }

  if ($i < @$set) {
    $bitMask->[$i] = 1;
    return 1;
  }

  return 0;
}

Note: I haven't been able to test the code, some bugs might need to be ironed out.

Answer 6

It's a counting problem - for N elements there are exactly 2^N subsets and you have to count from 0 to 2^N - 1 in binary to list them all.

For eg 3 items there are 8 possible subsets: 000, 001, 010, 011, 100, 101, 110 and 111 - the numbers show which members are present.