NAME

Set::CrossProduct - work with the cross product of two or more sets

SYNOPSIS

        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;

DESCRIPTION

Given sets S(1), S(2), ..., S(k), each of cardinality n(1), n(2), ..., n(k) respectively, the cross product of the sets is the set CP of ordered tuples such that { <s1, s2, ..., sk> | s1 => S(1), s2 => S(2), .... sk => S(k). }

If you do not like that description, how about:

Create a list by taking one item from each array, and do that for all possible ways that can be done, so that the first item in the list is always from the first array, the second item from the second array, and so on.

If you need to see it:

        A => ( a, b, c )
        B => ( 1, 2, 3 )
        C => ( foo, bar )

The cross product of A and B and C, A x B x C, is the set of tuples shown:

        ( a, 1, foo )
        ( a, 1, bar )
        ( a, 2, foo )
        ( a, 2, bar )
        ( a, 3, foo )
        ( a, 3, bar )
        ( b, 1, foo )
        ( b, 1, bar )
        ( b, 2, foo )
        ( b, 2, bar )
        ( b, 3, foo )
        ( b, 3, bar ) 
        ( c, 1, foo )
        ( c, 1, bar )
        ( c, 2, foo )
        ( c, 2, bar )
        ( c, 3, foo )
        ( c, 3, bar )

If one of the sets happens to be empty, the cross product is empty too.

        A => ( a, b, c )
        B => ( )
        

In this case, A x B is the empty set, so you'll get no tuples.

This module combines the arrays that give to it to create this cross product, then allows you to access the elements of the cross product in sequence, or to get all of the elements at once. Be warned! The cardnality of the cross product, that is, the number of elements in the cross product, is the product of the cardinality of all of the sets.

The constructor, new, gives you an iterator that you can use to move around the cross product. You can get the next tuple, peek at the previous or next tuples, or get a random tuple. If you were inclined, you could even get all of the tuples at once, but that might be a very large list. This module lets you handle the tuples one at a time.

I have found this module very useful for creating regression tests. I identify all of the boundary conditions for all of the code branches, then choose bracketing values for each of them. With this module I take all of the values for each test and create every possibility in the hopes of exercising all of the code. Of course, your use is probably more interesting. :)

METHODS

new( ARRAY_REF_OF_ARRAY_REFS )

Given the array of arrays that represent some sets, return a Set::CrossProduct instance that represents the cross product of those sets.

The single argument is an array reference that has as its elements other array references. The new method will return undef in scalar context and the empty list in list context if you give it something different.

You must have at least two sets, or the constructor will fail.

cardinality()

Return the carnality of the cross product. This is the number of tuples, which is the product of the number of elements in each set.

Strict set theorists will realize that this isn't necessarily the real cardinality since some tuples may be indentical, making the actual cardinality smaller.

reset_cursor()

Return the pointer to the first element of the cross product.

get()

Return the next tuple from the cross product, and move the position to the tuple after it.

In list context, get returns the tuple as a list. In scalar context get returns the tuple as an array reference.

If you have already gotten the last tuple in the cross product, then get returns undef in scalar context and the empty list in list context.

unget()

Pretend we did not get the tuple we just got. The next time we get a tuple, we will get the same thing. You can use this to peek at the next value and put it back if you do not like it.

You can only do this for the previous tuple. unget does not do multiple levels of unget.

next()

Return the next tuple, but do not move the pointer. This way you can look at the next value without affecting your position in the cross product.

In list context, get returns the tuple as a list. In scalar context get returns the tuple as an array reference.

For the last combination, next() returns undef.

previous()

Return the previous tuple, but do not move the pointer. This way you can look at the last value without affecting your position in the cross product.

In list context, get returns the tuple as a list. In scalar context get returns the tuple as an array reference.

done()

Without an argument, done returns true if there are no more combinations to fetch with get. and returns false otherwise.

With an argument, it acts as if there are no more arguments to fetch, no matter the value. If you want to start over, use reset_cursor instead.

random()

Return a random tuple from the cross product.

In list context, get returns the tuple as a list. In scalar context get returns the tuple as an array reference.

combinations()

Returns a reference to an arrray that contains all of the tuples of the cross product. This can be quite large, so you might want to check the cardinality first.

In list context, get returns the tuple as a list. In scalar context get returns the tuple as an array reference. However, you should probably always use this in scalar context except for very low cardnalities to avoid returning huge lists.

TO DO

* it would be nice to be able to name the sets, and then access elements from a tuple by name, like

        my $i = Set::CrossProduct->new( {
                        Apples => [ ... ],
                        Oranges => [ ... ],
                        }
                );

        my $tuple = $i->get;

        my $apple = $tuple->Apples;

* I need to fix the cardinality method. it returns the total number of possibly non-unique tuples.

BUGS

* none that i know about (yet)

SOURCE AVAILABILITY

This source is in Github:

        http://github.com/briandfoy/Set-CrossProduct

If, for some reason, I disappear from the world, one of the other members of the project can shepherd this module appropriately.

AUTHOR

brian d foy, <bdfoy@cpan.org>

COPYRIGHT AND LICENSE

Copyright (c) 2001-2010 brian d foy. All rights reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Set::CrossProduct

perl -MCPAN -e shell
install Set::CrossProduct