twenty four merry days of Perl Feed

Make all the combinations

Set::CrossProduct - 2011-12-06

You need to make combinations of things, but you don't want to create them all at once, or you can't create them all at once. You might only need one combination at a time.

I had this problem when I was creating a test suite for a legacy application. I need to test all of the boundary conditions for several functions. The return values for the new subroutines I was writing needed to be the same as those from the original:


1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 

 

my @tests = (
# INPUT_ARGS
[ qw( blood adanac 1 ) ],
  [ qw( blood adanac 2 ) ],
  [ qw( blood taylor 1 ) ],
  [ qw( blood taylor 2 ) ],
  [ qw( navel adanac 1 ) ],
# ... many more tuples
);

foreach my $tuple ( @tests ) {
  is(
    Original::foo( @$tuple ),
    New::foo( @$tuple ),
    "Arguments [ @$tuple ] returns the same thing"
    );
  }

 

This can be an effective way to write tests. The code that performs the actual tests is small and stays the same no matter how many tests I want to run. When I have more test cases, I add to the table of input values.

As the table got larger, listing all of the combinations literally in the code became a problem. I'd miss some combinations, repeat others, and even if I'd gotten everything right, I couldn't fit the table on a single screen.

I had specifically avoided nested loops. That might not annoy you when there are three or four parameters, but some of the subroutines took 15 parameters. That's a lot of nesting.

Instead, I wanted something where I could list the possible values for each of the positions, but without having to make all of the combinations myself. That is, I wanted a way to take a cross product of sets where each result would have one element from each set. Hence, Set::CrossProduct.


1: 
2: 
3: 
4: 
5: 
6: 
7: 

 

my $iterator = Set::CrossProduct->new(
  [
    [ qw( blood navel valencia ) ],
    [ qw( adanac taylor macintosh ) ],
    [ qw( 1 2 ) ]
  ]
  );

 

I can then use the iterator to get the next combination to check. The original implementation was the reference for correct, bug-for-bug behavior:


1: 
2: 
3: 
4: 
5: 
6: 
7: 

 

while( my $tuple = $iterator->get ) {
  is(
    New::foo( @$tuple ),
    Original::foo( @$tuple ),
    "Arguments [ @$tuple ] returns the same thing"
    );
  }

 

It's not a complicated module behind the scenes. For each of the array references, I maintain a cursor so I know which item to pick next. When I get to the end of an array reference, I go back to the start. If all the cursors are the last positions, then the iterator is spent.

The more I used the module, the more uses I found for it, and the more I needed to move around the iterator. Besides getting the next element, I added methods to look around the current combination, pick a random combination, or, get all of the combination at once (it came full circle):


1: 
2: 
3: 
4: 
5: 
6: 
7: 
8: 
9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 

 

my $iterator = Set::CrossProduct->new( ARRAY_OF_ARRAYS );

# get the number of tuples
my $number_of_tuples = $iterator->cardinality;

# get the next tuple
my $tuple = $iterator->get;

# move back one position
my $tuple = $iterator->unget;

# get the next tuple without resetting
# the cursor (peek at it)
my $next_tuple = $iterator->next;

# get the previous tuple without resetting
# the cursor
my $last_tuple = $iterator->previous;

# get a random tuple
my $tuple = $iterator->random;

# in list context returns a list of all tuples
my @tuples = $iterator->combinations;

# in scalar context returns an array reference to all tuples
my $tuples = $iterator->combinations;

 

See Also

The Set::CrossProduct module isn't the only way to accomplish this task. The Algorithm::Loops module has a NestedLoops subroutine that can do the same thing.

Some people confuse a cross product of different sets with permutations of elements in the same set. If that's what you want to do, Algorithm::Combinatorics might be the right tool.

Gravatar Image This article contributed by: brian d foy <bdfoy@cpan.org>