View on
brian d foy > Set-CrossProduct-2.002 > Set::CrossProduct



Annotate this POD


Related Modules

View/Report Bugs
Module Version: 2.002   Source  


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


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

        # or labeled sets where hash keys are the set names
        my $iterator = Set::CrossProduct->new( HASH_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;


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 cardinality 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. :)



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

* I'd also like to do something like this:

        use Set::CrossProduct qw(setmap);

        # use setmap with an existing Set::CrossProduct object
        my @array = setmap { ... code ... } $iterator;

        # use setmap with unnamed arrays
        my @array = setmap { [ $_[0], $_[1] ] }
                key => ARRAYREF, key2 => ARRAYREF;

        # use setmap with named arrays
        my @array = setmap { [ $key1, $key2 ] }
                key => ARRAYREF, key2 => ARRAYREF;

        # call apply() with a coderef. If the object had labels
        # (constructed with a hash), you can use those labels in
        # the coderef.
        $set->apply( CODEREF );


* none that i know about (yet)


This source is in Github:

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


brian d foy, <>

Matt Miller implemented the named sets feature.


Copyright © 2001-2016, 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.

syntax highlighting: