Re: fixed list combinatorics

On Nov 28, 2007, at 10:37 PM, Xavier Noria wrote:

On Nov 28, 2007, at 9:54 PM, Xavier Noria wrote:

On Nov 28, 2007, at 8:58 PM, yitzle wrote:

In a personal email conversation, he realized what he was actually
looking for is the power set.
List::PowerSet
http://search.cpan.org/~nikc/List-PowerSet-0.01/lib/List/PowerSet.pm

If speed is an issue Algorith::Combinatorics provides subsets() in XS:

I had done some benchmarks which are included in the distribution but not this one.

I've found that List::PowerSet outperforms Algorithm::Combinatorics' subset(). Time to revise that subroutine.

Indeed, the iterator provided by Algorithm::Combinatorics is faster only for lists of sizes >= 7. (And gets to be twice as fast for size 16.)

The subroutine that gives you all the subsets in one shot has its own implementation in List::PowerSet (it is not a wrapper around the iterator). It is recursive and fast, and clever! I think it is that fast because it actually runs basically in C:

[ map { [$first, @$_ ], [ @$_] } @$pow ];

given that map is an opcode.

For that call Algorithm::Combinatorics matches and performs slighly better than List::PowerSet from size 14 on. I guess that's because it creates less intermediate stuff.

Certainly there's room for improvement here.

-- fxn

.