PHP - Generating all possible combinations of given charactrers

Question

Update:

Yes I got that part that it's not recommended to store everything in single array. I added a limit of 5000 combinations at a time but there is a new problem.

I can get first 5000 combinations but I can't think of anything to generate rest of the combinations (5001 to 10000, 10001 to 15000 and so on)

To generate first 5000 combinations, I'm using a variable that gets increased by 1 every time the loop runs and when the variable exceeds 5000, the loop is stopped and result is printed. However after 5000, if I have to generate the next 5000 combinations, the loop will have to generate first 5000 combinations too before reaching to the next 5000 combinations and this again will consume memory unnecessarily.

Hope that made sense.

I want to generate all possible combination like this:

Input:

array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),

Desired Output:

I'm currently using this code to generate the combinations:

<?php
ini_set('display_errors', 1);
ini_set('display_startup_errors', 1);
error_reporting(E_ALL);
$string = '';
function combinations($arrays, $i = 0) {
    if (!isset($arrays[$i])) {
        return array();
    }
    if ($i == count($arrays) - 1) {
        return $arrays[$i];
    }

    // get combinations from subsequent arrays
    $tmp = combinations($arrays, $i + 1);

    $result = array();

    // concat each array from tmp with each element from $arrays[$i]
    foreach ($arrays[$i] as $v) {
        foreach ($tmp as $t) {
            $result[] = is_array($t) ? 
                array_merge(array($v), $t) :
                array($v, $t);
        }
    }

    return $result;
}

$array =    combinations(
        array(
           array('1','2','3','4','5'),
     array('1','2','3','4','5'),
     array('1','2','3','4','5'),
     array('1','2','3','4','5'),
        )
    );
foreach( $array as $combinations1 => $numbers )
{
     foreach( $numbers as $number )
  {
   $string .= $number;
  }
  echo $string.'<br/>'; 
  
  
  $string = ''; //unload
  
  }
?>

This code works if input is small but for larger inputs like:

array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),
array('1','2','3','4','5'),

the code throws the following error:

Fatal error: Allowed memory size of 67108864 bytes exhausted (tried to allocate 72 bytes)

Is there any better way to do what I want?

Thanks in Advance :)

Possible duplicate of [Generating all permutations of a given string](http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) — r3wt, Feb 10 '16 at 14:32
Well, the error is clear. Though it doesn't depend directly from your code. It means your script is using more memory than PHP is allowed to allocate, you can either change this setting from your php.ini file or optimize your code to use less memory (as starter you don't need to save all the combinations in an array but you can print them as soon as they are generated) — valepu, Feb 10 '16 at 14:33
Do you know how many `combinations` does your `large input` make? More than 240 Million. How do you expect to store them in the limited memory that your script gets, even if you manage to finish the loop in any reasonable amount of time — Hanky Panky, Feb 10 '16 at 14:47
See this [code](http://codereview.stackexchange.com/questions/41510/calculate-all-possible-combinations-of-given-characters). Please note that using array with undefined (unlimited) rows, can **however** exhaust memory (also increasing memory limit) — fusion3k, Feb 10 '16 at 15:27
@r3wt That question does not answer my query at all. I don't know how this question is a possible duplicate of that one. — newBB, Feb 10 '16 at 15:53
your second example has 5^12=244140625 *permutations*, each one of which would need at least 12 bytes for plain text - without any overhead, without any output buffer, without anything at all. which amounts to 2.7GiB - which is a little more than the 64MiB your PHP has. so, if you want to store *all* of those permutations, you have to find more space. for example on your harddrive, pushing one line after the other, so your RAM stays free most of the time. — Franz Gleichmann, Feb 10 '16 at 16:56

score 2 · Answer 1 · answered Feb 10 '16 at 14:33

2

why not just some nested loops?

$arr1 = array(1,2,3,4,5);
$arr2 = array(1,2,3,4,5);
...
$arrN = array(1,2,3,4,5);

$result = array();
foreach($arr1 as $val1) {
   foreach($arr2 as $val2) {
       ...
       foreach($arrN as $valN) {
           $result[] = array($val1, $val2, ..., $valN);
       }
    }
}

answered Feb 10 '16 at 14:33

Marc B

356,200
43
426
500

Doesn't the problem with *input* still remain there? For example OP's 12 arrays with 5 elements each will make this loop set have 244140625 iterations which is again good enough to consume a lot of memory – Hanky Panky Feb 10 '16 at 14:37
then OP needs to explain how the array's being used. if it's just to build a list of the all the variations, then they can be written out to a file and not stored in an array. but that's a minor problem v.s. actually building the list. – Marc B Feb 10 '16 at 14:38
Problem is that the OP's actual demand from this algorithm is not really sustainable for that long an input. Asking PHP to write 240 million different numbers in a file in one go will be a problem one way or another. If memory consumption gets controlled then resource and time usage will still remain a problem with that example input. It's like asking for *too much* – Hanky Panky Feb 10 '16 at 14:42
but only one result list would be in memory at any given time, so if the base arrays fit in there, you'd only a few extra hundred-ish bytes to store the resulting combinations. store one row, dump to disk, start another row. – Marc B Feb 10 '16 at 14:49
Thanks for your answer. Your code is much better than mine. Please check my updated question. – newBB Feb 10 '16 at 16:04

PHP - Generating all possible combinations of given charactrers

1 Answers1

Linked

Related