# All possibilities from datasets? How to?

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
We have X number of data sets, of Y length each.

For example...

Small, Medium, Large
and
Red, Green, Blue, Yellow

We need to generate a list of all possibilities
Small Red
Small Green
Small Blue
Small Yellow
Medium Red
Medium Green
... etc.

The catch...
There can be any number of data sets, and they can be of any length.

Any idea on the algorithm to do this?

I've seen some examples where they just have several nested for loops,
but there could be any number of datasets.

Any help is appericated!

## Re: All possibilities from datasets? How to?

gardnern wrote:

Recursivity.

--
----------------------------------
Iván Sánchez Ortega -ivan-algarroba-sanchezortega-punto-es-

Now listening to: SEBRIDER - Heaven and Sea - [4] Whales' Song (6:18)
(97.384598%)

## Re: All possibilities from datasets? How to?

gardnern wrote:

Are these permutations or combinations

In other words, is Small Red different from Red Small?

## Re: All possibilities from datasets? How to?

wrote:

Combinations, not permutations.

## Re: All possibilities from datasets? How to?

Try this then:

\$datasets = array();
\$datasets[] = array('Small', 'Medium', 'Large');
\$datasets[] = array('Red', 'Green', 'Blue', 'Yellow');

while (\$leftset = array_shift(\$datasets))
foreach (\$leftset as \$left)
foreach (\$datasets as \$rightset)
foreach (\$rightset as \$right)
echo " <br />";

## Re: All possibilities from datasets? How to?

thats fine if theres only 2 datasets, but what if theres 20 of them?
nested foreach loops wont work. I know I have to use recursion, but
not sure how...

## Re: All possibilities from datasets? How to?

gardnern wrote:

select X.x, Y.y, Z.z  (etc.) from X, Y, Z (etc.)  order by x, y, z (etc.) ?

You could construct this statement in a loop where you have the tables
and fields in an array.  That way SQL will do all the work for you.

## Re: All possibilities from datasets? How to?

If you're dealing with 20 datasets then the odds are your script will
time out long before the operation completes.  The problem you're
describing is of a kind that has exponential run time.  Lets say you
have 2 sets of 256 elements each.  To get all possible combinations
will take 65536 iterations.  Quite a lot but managable on modern
hardware.  Now, lets say you have 3 sets of 256 elements.  You're now
will result in 4294967296 iterations, 5 sets will mean 1099511627776
iterations, 6 sets will mean 281474976710656 iterations, 7 sets will
mean 72057594037927936 iterations... When you hit 20 sets the number
my calculator spits out is so big it needs to be written in scientific
notation (1.4615016373309029182036848327163e+48, if you're curious).

Even with much smaller sets, the number of sets will cause the
possible permutations to grow exponentially, for example even with
only 8 elements per set the result is 1152921504606846976 possible
permutations of 20 sets.

At the risk of sounding rude (which is honestly not my intent), I
think you might need to take a careful look at what it is you're
actually trying to achieve, as it looks like there could be something
of it.  You need to be thinking "How can I achieve what I want without
having to do it by brute force?" instead of "How do I implement the
brute force way of doing this?"

## Re: All possibilities from datasets? How to?

This isn't something that will be running often, its used to generate
all possible SKUs for products with every combination of its options.
I found a solution and its working great. Even with 3 (lengths
100,5,9) it only takes 0.23 seconds on a slow machine.

Heres the solution, for reference....

<?php

\$startTime = microtime(true);

function arrays_mix(){

// This is an array that adds a new
// element each time we are starting
// with a new parent element in the hierarchy
static \$parents;
global \$mixedArrays;
\$combinations = array();
\$args = func_get_args();
\$values = array_shift(\$args);

if(!empty(\$args)){

foreach(\$values as \$value){

\$parents[] = \$value;
call_user_func_array("arrays_mix", \$args);

// Remove this parent from the array. We need
// a reorganized index so we use array_pop()
array_pop(\$parents);

}

} else {

foreach(\$values as \$value){

\$mixedArrays[] = implode(", ",\$parents).", ".\$value;

}

}

return \$mixedArrays;

}

\$sizes = range(0,100);
\$widths = array('SS','S','W','M','XW');
\$colors =
array('red','green','blue','yellow','orange','black','brown','white','trans=
parent');
\$result = arrays_mix(\$sizes,\$widths,\$colors);

echo '<pre>';
print_r(\$result);
echo '</pre>';

\$endTime = microtime(true);

echo 'Took '.number_format(\$endTime - \$startTime,2).' seconds, and php
used '.((memory_get_peak_usage(true)/1024)/1024).'MB of memory';

?>

## Re: All possibilities from datasets? How to?

Glanced at your code quickly.  Seems that it's working over the data
structures recursively.  I noticed you mentioned datasets of 100, 5
and 9 elements. The sums say the result of processing that amount of
state is 4500 iterations.

If this works okay for you then fair enough. :)  Just be careful about
the data you feed into this function, as simply adding a 4th array
with 2 elements will double the runtime, or adding a 4th array with 10
elements will increase it 10 fold. Taking the run time you quoted this
would result in 2.3 seconds of run time.  A 5th 10 element array will
push this up to 23 seconds, dangerously close to the PHP 30 seconds
default runtime limit.

## Re: All possibilities from datasets? How to?

.oO(gardnern)

If you have a function to combine two datasets A and B:

R1 = A + B

just call it again to add another one:

R2 = R1 + C = (A + B) + C

Nothing special. Of course the combine function should return the result
in a way so that it can be used as an input again.

Micha