NAME
Set::CrossProduct - work with the cross product of two or more sets
SYNOPSIS
# 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;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 )In code, it looks like this:
use v5.26;
use Set::CrossProduct;
my $cross = Set::CrossProduct->new( {
A => [ qw( a b c ) ],
B => [ qw( 1 2 3 ) ],
C => [ qw( foo bar ) ],
} );
while( my $t = $cross->get ) {
printf "( %s, %s, %s )\n", $t->@{qw(A B C)};
}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. :)
Class Methods
new( [ [ ... ], [ ... ] ])
new( { LABEL => [ ... ], LABEL2 => [ ... ] } )
Given arrays that represent some sets, return a
Set::CrossProductinstance that represents the cross product of those sets. If you don't provide at least two sets,newreturns undef and will emit a warning if warnings are enabled.You can create the sets in two different ways: unlabeled and labeled sets.
For unlabeled sets, you don't give them names. You rely on position. To create this, pass an array of arrays:
my $unlabeled = Set::CrossProduct->new( [ [ qw(1 2 3) ], [ qw(a b c) ], [ qw(! @ $) ], ] );When you call
next, you get an array ref where the positions in the tuple correspond to the position of the sets you gavenew:my $tuple = $unlabeled->next; # [ qw(1 a !) ]For labeled sets, you want to give each set a name. When you ask for a tuple, you get a hash reference with the labels you choose:
my $labeled = Set::CrossProduct->new( { number => [ qw(1 2 3) ], letter => [ qw(a b c) ], symbol => [ qw(! @ $) ], } ); my $tuple = $labeled->next; # { number => 1, letter => 'a', symbol => '!' }
Instance methods
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 identical, making the actual cardinality smaller.
combinations()
In scalar context, returns a reference to an array that contains all of the tuples of the cross product. In list context, it returns the list of all tuples. You should probably always use this in scalar context except for very low cardinalities to avoid huge return values.
This can be quite large, so you might want to check the cardinality first. The array elements are the return values for
get.done()
Without an argument,
donereturns true if there are no more combinations to fetch withgetand 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_cursorinstead.get()
Return the next tuple from the cross product, and move the position to the tuple after it. If you have already gotten the last tuple in the cross product, then
getreturns undef in scalar context and the empty list in list context.What you get back depends on how you made the constructor.
For unlabeled sets, you get back an array reference in scalar context or a list in list context:
For labeled sets, you get back a hash reference in scalar context or a list of key-value pairs in list context.
labeled()
Return true if the sets are labeled (i.e. you made the object from a hash ref). Returns false otherwise. You might use this to figure out what sort of value
getwill return.next()
Like
get, but does not move the pointer. This way you can look at the next tuple without affecting your position in the cross product.previous()
Like
get, but does not move the pointer. This way you can look at the previous tuple without affecting your position in the cross product.random()
Return a random tuple from the cross product. The return value is the same as
get.reset_cursor()
Return the pointer to the first element of the cross product.
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.
ungetdoes not do multiple levels of unget.
TO DO
* 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 );BUGS
* none that I know about (yet)
SOURCE AVAILABILITY
This source is in Github:
http://github.com/briandfoy/set-crossproductAUTHOR
brian d foy, <briandfoy@pobox.com>
Matt Miller implemented the named sets feature.
COPYRIGHT AND LICENSE
Copyright © 2001-2024, brian d foy <briandfoy@pobox.com>. All rights reserved.
This program is free software; you can redistribute it and/or modify it under the terms of the Artistic License 2.0.