All possibilities from datasets? How to?

[gardnern]

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!

[=?UTF-8?B?SXbDoW4gU8OhbmNoZXogT3J0ZWdh?=]

Re: All possibilities from datasets? How to?

gardnern wrote:

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

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%)

[Paul Lautman]

Re: All possibilities from datasets? How to?

gardnern wrote:

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!

Are these permutations or combinations

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

[gardnern]

Re: All possibilities from datasets? How to?

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:

gardnern wrote:

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!

>
Are these permutations or combinations
>
In other words, is Small Red different from Red Small?

Combinations, not permutations.

[Captain Paralytic]

Re: All possibilities from datasets? How to?

On 29 Jul, 15:12, gardnern <nat...@factory 8.comwrote:

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:
>
>
>
>
>

gardnern wrote:

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!

>

Are these permutations or combinations

>

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

>
Combinations, not permutations.- Hide quoted text -
>
- Show quoted text -

Try this then:

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

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

[gardnern]

Re: All possibilities from datasets? How to?

On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@y ahoo.comwrote:

On 29 Jul, 15:12, gardnern <nat...@factory 8.comwrote:
>
>
>

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:

>

gardnern wrote:
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!

>

Are these permutations or combinations

>

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

>

Combinations, not permutations.- Hide quoted text -

>

- Show quoted text -

>
Try this then:
>
$datasets = array();
$datasets[] = array('Small', 'Medium', 'Large');
$datasets[] = array('Red', 'Green', 'Blue', 'Yellow');
>
while ($leftset = array_shift($da tasets))
  foreach ($leftset as $left)
    foreach ($datasets as $rightset)
       foreach ($rightset as $right)
         echo "{$left} {$right}<br />";

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...

[Gordon]

Re: All possibilities from datasets? How to?

On Jul 29, 3:56 pm, gardnern <nat...@factory 8.comwrote:

On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@y ahoo.comwrote:
>
>
>

On 29 Jul, 15:12, gardnern <nat...@factory 8.comwrote:

>

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:

>

gardnern wrote:
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!

>

Are these permutations or combinations

>

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

>

Combinations, not permutations.- Hide quoted text -

>

- Show quoted text -

>

Try this then:

>

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

>

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

>
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...

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
talking about 16777216 iterations. Adding another set of 256 elements
will result in 4294967296 iterations, 5 sets will mean 1099511627776
iterations, 6 sets will mean 281474976710656 iterations, 7 sets will
mean 720575940379279 36 iterations... When you hit 20 sets the number
my calculator spits out is so big it needs to be written in scientific
notation (1.461501637330 902918203684832 7163e+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 115292150460684 6976 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
wrong with your design, or at least with your planned implementation
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?"

[gardnern]

Re: All possibilities from datasets? How to?

On Jul 29, 11:41 am, Gordon <gordon.mc...@n tlworld.comwrot e:

On Jul 29, 3:56 pm, gardnern <nat...@factory 8.comwrote:
>
>
>

On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@y ahoo.comwrote:

>

On 29 Jul, 15:12, gardnern <nat...@factory 8.comwrote:

>

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:

>

gardnern wrote:
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 forloops,
but there could be any number of datasets.

>

Any help is appericated!

>

Are these permutations or combinations

>

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

>

Combinations, not permutations.- Hide quoted text -

>

- Show quoted text -

>

Try this then:

>

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

>

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

>

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...

>
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
talking about 16777216 iterations.  Adding another set of 256 elements
will result in 4294967296 iterations, 5 sets will mean 1099511627776
iterations, 6 sets will mean 281474976710656 iterations, 7 sets will
mean 720575940379279 36 iterations... When you hit 20 sets the number
my calculator spits out is so big it needs to be written in scientific
notation (1.461501637330 902918203684832 7163e+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 115292150460684 6976 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
wrong with your design, or at least with your planned implementation
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?"

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($ar gs);

if(!empty($args )){

foreach($values as $value){

$parents[] = $value;
call_user_func_ array("arrays_m ix", $args);

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

}

} 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','gr een','blue','ye llow','orange', 'black','brown' ,'white','trans parent');
$result = arrays_mix($siz es,$widths,$col ors);

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';

?>

[Michael Fesser]

Re: All possibilities from datasets? How to?

..oO(gardnern)

>On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@y ahoo.comwrote:

>>
>$datasets = array();
>$datasets[] = array('Small', 'Medium', 'Large');
>$datasets[] = array('Red', 'Green', 'Blue', 'Yellow');
>>
>while ($leftset = array_shift($da tasets))
>  foreach ($leftset as $left)
>    foreach ($datasets as $rightset)
>       foreach ($rightset as $right)
>         echo "{$left} {$right}<br />";

>
>
>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...

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

[Gordon]

Re: All possibilities from datasets? How to?

On Jul 29, 6:05 pm, gardnern <nat...@factory 8.comwrote:

On Jul 29, 11:41 am, Gordon <gordon.mc...@n tlworld.comwrot e:
>
>
>

On Jul 29, 3:56 pm, gardnern <nat...@factory 8.comwrote:

>

On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@y ahoo.comwrote:

>

On 29 Jul, 15:12, gardnern <nat...@factory 8.comwrote:

>

On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@b tinternet.com>
wrote:

>

gardnern wrote:
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!

>

Are these permutations or combinations

>

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

>

Combinations, not permutations.- Hide quoted text -

>

- Show quoted text -

>

Try this then:

>

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

>

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

>

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...

>

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
talking about 16777216 iterations.  Adding another set of 256 elements
will result in 4294967296 iterations, 5 sets will mean 1099511627776
iterations, 6 sets will mean 281474976710656 iterations, 7 sets will
mean 720575940379279 36 iterations... When you hit 20 sets the number
my calculator spits out is so big it needs to be written in scientific
notation (1.461501637330 902918203684832 7163e+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 115292150460684 6976 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
wrong with your design, or at least with your planned implementation
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?"

>
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($ar gs);
>
        if(!empty($args )){
>
                foreach($values as $value){
>
                        $parents[] = $value;
                        call_user_func_ array("arrays_m ix", $args);
>
                        // Remove this parent from the array. We need
                        // a reorganized index sowe use array_pop()
                        array_pop($pare nts);
>
                }
>
        } 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','gr een','blue','ye llow','orange', 'black','brown' ,'white','trans parent');
$result = arrays_mix($siz es,$widths,$col ors);
>
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';
>
?>

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.