PHP上的排列/组合 [英] Permutations/combinations on PHP

问题描述

我正在尝试编写一个脚本来执行从0到45的6个数字的所有排列/组合，没有重复，但是它不起作用，因为有些数字在同一行重复.

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.

我做错了什么?

代码:

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:

致命错误:允许的内存大小为33554432字节已用尽(尝试分配2348617字节)

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);
?>

我做错了什么?

谢谢

推荐答案

这将生成所有排列(不是组合):

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";
        }
    }
}

它从m选项中选择n个单词，从而获得m! / (m-n)!结果.对于n=3和m=5，您将得到60. 45!/39!给出5,864,443,200.

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.

由于您希望输出为csv，因此可以对其进行修改:

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

这根本不会占用太多内存.它的上限为$num*$words个元素，应该在1mb以下(深度优先为佳，广度优先为佳).现在输出文件将是巨大的:P

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

我不知道生成此文件将花费多长时间.我建议您运行一些测试.您可能需要set_time_limit(0);来给脚本无限的时间，但是首先尝试使用较小的值(或者准备终止该脚本).可能有一些方法可以使其更快，某些阵列逻辑并不是特别快.

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.

这篇关于PHP上的排列/组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！