Permutations/combinations on PHP

Question

I'm trying to do a script to perform all the permutations/combinations for 6 numbers from 0 to 45, without repetitions, but it's not working because some numbers repets in the same line.

What i'm doing wrong?

CODE:

for($a=0; $a<45-5; $a++)
    for($b=$a+1; $b<45-4; $b++)
        for($c=$b+1; $c<45-3; $c++)
            for($d=$c+1; $d<45-2; $d++)
                for($e=$d+1; $d<45-1; $d++)
                    for($f=$e+1; $d<45; $d++)
                echo "$a $b $c $d $e $f \n";

I'm testing another code but I receive this error:

Fatal error: Allowed memory size of 33554432 bytes exhausted (tried to allocate 2348617 bytes)

<?php
function permutations($arr,$n)
{
     $res = array();

     foreach ($arr as $w)
     {
           if ($n==1) $res[] = $w;
           else
           {
                 $perms = permutations($arr,$n-1);

                 foreach ($perms as $p)
                 {
                      $res[] = $w." ".$p."<p>";
                 } 
           }
     }

     return $res;
}

$words = array('00','01','02','03','04','05','06','07','08','09','10','11','12','13','14','15','16','17','18','19','20','21','22','23','24','25','26','27','28','29','30','31','32','33','34','35','36','37','38','39','40','41','42','43','44','45');

$pe = permutations($words,6);

print_r($pe);
?>

What I'm doing wrong?

Thank you

So `00 01 02..` and `01 00 02..` should both occur, but not `00 00 01`? Keep in mind that 45^6 is around 8 billion. Do you really need 8 billion results? You're surely going to run out of memory. — Halcyon, Feb 12 '15 at 15:46
Yes, I need all the combinations without repetitions of any number. I know there are almost 9 millons of combinations, but I need to insert all those numbers into a database or into a csv or text file. — oknarf, Feb 12 '15 at 16:04

Halcyon · Answer 1 · 2015-02-13T14:40:30.383

This will generate all permutations (not combinations):

$words = array("00", "01", "02", "03", "04");

pick($words, 3);

function pick($words, $num, $picked = array()) {
    for ($i = 0; $i < count($words); $i += 1) {
        $word = $words[$i];
        $remaining_words = array_diff($words, array($word));
        if ($num > 1) {
            // pick the remaning $num-1 words
            pick(array_values($remaining_words), $num - 1, array_merge($picked, array($word)));
        } else {
            echo implode(",", array_merge($picked, array($word))) . "\n";
        }
    }
}

It picks n words from m options so you get m! / (m-n)! results. For n=3 and m=5 you get 60. 45!/39! gives 5,864,443,200.

Since you want the output as csv you can modify it:

$handle = fopen("perms.csv", "w");

// code

    // instead of echo:
    fputcsv($handle, array_merge($picked, array($word)));

// end code

fclose($handle);

This shouldn't consume much memory at all. It will have an upper limit of $num*$words elements, which should be well under 1mb (depth first is good, breadth first would be terrible). Now the output file will be huge :P

I have no idea how long it will take to generate this file. I recommend you run some tests. You will likely need set_time_limit(0); to give your script unlimited time but experiment with lower values first (or be ready to kill the script). There may be ways to make it faster, some of the array logic is not particularly fast.

score 0 · Answer 2 · answered Feb 12 '15 at 16:00

Your first program has some typos: the for loops for $e and $f contain $d. If I change this, the output of this program looks ok to me. It finds 8145060 permutations.

Your second solutions works with recursion, which is obviously too deeply nested so it excceds the memory you have.

Xeridea · Answer 3 · 2015-02-12T16:06:05.287

0

PHP uses 72 bytes of memory minimum per variable, 8 billion results would take about 600 gigs of ram. PHP7, aka PHPNG reduces this to 56 bytes, but this wouldn't help much in your situation. Even in a compiled language it would be large.

When I have done combinations of words in the past where a lot of results were needed, I ended up having it write to a file, so it processes chunks of data and writes to a file in batches. It is more complex code, but it is necessary for doing this sort of thing.

Another thing you can do for working with large datasets is, if you don't need them all easily accessible and can work in chunks, you can json encode sets of arrays, so it doesn't incur the per variable overhead. In your case though, this would still be futile.

Looks like you have PHP allowed 32MB of RAM, if this is a controlled environment, you could call:

ini_set('memory_limit','256M');

to set the max memory of the current script. Even so, you will run out of memory and will need to refactor code.

edited Feb 12 '15 at 16:06

answered Feb 12 '15 at 16:00

Xeridea

1,146
1
10
17

I modify the code, but still does not work properly: for($a=0; $a<45-5; $a++) for($b=$a+1; $b<45-4; $b++) for($c=$b+1; $c<45-3; $c++) for($d=$c+1; $d<45-2; $d++) for($e=$d+1; $e<45-1; $e++) for($f=$e+1; $f<45; $f++) echo "$a $b $c $d $e $f \n"; How can I send the result to csv, txt or another file? Thank you – oknarf Feb 12 '15 at 16:34
Look up PHP **fopen**, and PHP **fputcsv** for official docs. Then I would have the innermost loop add to an array rather than echoing, and perhaps the "d" loop would write to csv file, or text file. For faster testing, i would reduce the 45 to say 10. On the recursive method, you could base file writing on how deep it is. – Xeridea Feb 12 '15 at 17:11

Permutations/combinations on PHP

3 Answers3

Linked