471,120 Members | 1,382 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,120 software developers and data experts.

All possibilities from datasets? How to?

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!
Jul 28 '08 #1
9 1794
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%)
Jul 28 '08 #2
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?
Jul 28 '08 #3
On Jul 28, 5:26*pm, "Paul Lautman" <paul.laut...@btinternet.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.
Jul 29 '08 #4
On 29 Jul, 15:12, gardnern <nat...@factory8.comwrote:
On Jul 28, 5:26*pm, "Paul Lautman" <paul.laut...@btinternet.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($datasets))
foreach ($leftset as $left)
foreach ($datasets as $rightset)
foreach ($rightset as $right)
echo "{$left} {$right}<br />";
Jul 29 '08 #5
On Jul 29, 9:38*am, Captain Paralytic <paul_laut...@yahoo.comwrote:
On 29 Jul, 15:12, gardnern <nat...@factory8.comwrote:
On Jul 28, 5:26*pm, "Paul Lautman" <paul.laut...@btinternet.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($datasets))
* 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...
Jul 29 '08 #6
On Jul 29, 3:56 pm, gardnern <nat...@factory8.comwrote:
On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@yahoo.comwrote:
On 29 Jul, 15:12, gardnern <nat...@factory8.comwrote:
On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@btinternet.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($datasets))
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 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
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?"
Jul 29 '08 #7
On Jul 29, 11:41*am, Gordon <gordon.mc...@ntlworld.comwrote:
On Jul 29, 3:56 pm, gardnern <nat...@factory8.comwrote:
On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@yahoo.comwrote:
On 29 Jul, 15:12, gardnern <nat...@factory8.comwrote:
On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@btinternet.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($datasets))
* 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 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
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($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','blac k','brown','white','transparent');
$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';

?>
Jul 29 '08 #8
..oO(gardnern)
>On Jul 29, 9:38*am, Captain Paralytic <paul_laut...@yahoo.comwrote:
>>
$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 "{$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
Jul 29 '08 #9
On Jul 29, 6:05*pm, gardnern <nat...@factory8.comwrote:
On Jul 29, 11:41*am, Gordon <gordon.mc...@ntlworld.comwrote:
On Jul 29, 3:56 pm, gardnern <nat...@factory8.comwrote:
On Jul 29, 9:38 am, Captain Paralytic <paul_laut...@yahoo.comwrote:
On 29 Jul, 15:12, gardnern <nat...@factory8.comwrote:
On Jul 28, 5:26 pm, "Paul Lautman" <paul.laut...@btinternet.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($datasets))
* 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 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
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($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 sowe 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','blac k','brown','white','transparent');
$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';

?>
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.
Jul 30 '08 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

reply views Thread by William Ryan | last post: by
9 posts views Thread by GaryDean | last post: by
4 posts views Thread by Ronald S. Cook | last post: by
25 posts views Thread by Penelope Dramas | last post: by
2 posts views Thread by S.Tedeschi | last post: by
12 posts views Thread by BillE | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.