All k partitions

#!/bin/perl
#
# Enumerate all the partitions of {1, 3, 4, 5, 7, 15, 16, 17, 21, 23, 25, 31}
# into 4 subsets.
#
# Samuel DEVULDER, fev 2014
#

# 1st: the set
$set = 0;
for my $x (1, 3, 4, 5, 7, 15, 16, 17, 21, 23, 25, 31) {$set |= 1<<$x;}

# 2nd: the number of partitions
$num = 4;

# 3rd: enumerate all
$n = 0;
for $part (&all_k_partition($num, $set, 0)) {
    print ++$n, " ";
    for my $subset (split(',', $part)) {&print_set($subset);}
    print "\n";
}

sub print_set {
    my($set) = @_;

    print "{";
    my($first) = 1;
    for(my $i=0; (1<<$i)<=$set; ++$i) {
        if($set & (1<<$i)) {
            print "," unless $first; $first = 0;
            print $i;
        }
    }
    print "} ";
}

sub next_in_set {
        my($x, $set) = @_;
        return ($x-$set) & $set;
}

sub all_k_partition {
        my($k, $set, $i) = @_;
        return () if $set==0 || $k==0 || $set<=$i;
        return ($set) if $k==1;

        my(@r);
        while($i = &next_in_set($i, $set)) {
                my($m) = $i;
                for (my $j = 1;$m>>$j;$j<<=1) {$m|=$m>>$j;}
                for my $j (&all_k_partition($k-1, $set^$i, $m)) {
                        push(@r, "$i,$j");
                }
        }

        return @r;
}