Php递归以获得字符串的所有可能性

Question

这是我的代码,以获得所有可能性:

$seq[1] = 'd';
$seq[2] = 'f';
$seq[3] = 'w';
$seq[4] = 's';

for($i = 1; $i < 5; $i++)
{
    $s['length_1'][] = $seq[$i];
    $c1++;

    for($i2 = $i+1; $i2 < 5; $i2++)
    {
        $s['length_2'][] = $seq[$i].$seq[$i2]; 
        $last = $seq[$i].$seq[$i2]; 
        $c2++;

        for($i3 = $i2+1; $i3 < 5; $i3++)
        { 
            $s['length_3'][] = $last.$seq[$i3];
            $last = $last.$seq[$i3];    
            $c3++;

            for($i4 = $i3+1; $i4 < 5; $i4++)
            {
                $s['length_4'][] = $last.$seq[$i4];   
                $c4++;  
            }
        }
    }
}

for($i = 0; $i < $c1; $i++)
    echo $s['length_1'][$i].'<br>'; 

for($i = 0; $i < $c2; $i++)
    echo $s['length_2'][$i].'<br>';   

for($i = 0; $i < $c3; $i++)
    echo $s['length_3'][$i].'<br>';  

for($i = 0; $i < $c4; $i++)
    echo $s['length_4'][$i].'<br>';    

但如果我想添加更多,那么我将不得不再添加一个循环.那么,我怎么能用递归来做呢？我尝试,我尝试,但我真的不能这样做.请尽可能简单地帮助和发布示例.

谢谢.

Answer 1

一种算法在这里,

function getCombinations($base,$n){

$baselen = count($base);
if($baselen == 0){
    return;
}
    if($n == 1){
        $return = array();
        foreach($base as $b){
            $return[] = array($b);
        }
        return $return;
    }else{
        //get one level lower combinations
        $oneLevelLower = getCombinations($base,$n-1);

        //for every one level lower combinations add one element to them that the last element of a combination is preceeded by the element which follows it in base array if there is none, does not add
        $newCombs = array();

        foreach($oneLevelLower as $oll){

            $lastEl = $oll[$n-2];
            $found = false;
            foreach($base as  $key => $b){
                if($b == $lastEl){
                    $found = true;
                    continue;
                    //last element found

                }
                if($found == true){
                        //add to combinations with last element
                        if($key < $baselen){

                            $tmp = $oll;
                            $newCombination = array_slice($tmp,0);
                            $newCombination[]=$b;
                            $newCombs[] = array_slice($newCombination,0);
                        }

                }
            }

        }

    }

    return $newCombs;


}

我知道它在任何方面都没有效果,但在小套装中使用应该不是问题

first base参数是一个数组,包含生成组合时要考虑的元素.

用于简单的使用和输出:

var_dump(getCombinations(array("a","b","c","d"),2));

和输出是

array
  0 => 
    array
      0 => string 'a' (length=1)
      1 => string 'b' (length=1)
  1 => 
    array
      0 => string 'a' (length=1)
      1 => string 'c' (length=1)
  2 => 
    array
      0 => string 'a' (length=1)
      1 => string 'd' (length=1)
  3 => 
    array
      0 => string 'b' (length=1)
      1 => string 'c' (length=1)
  4 => 
    array
      0 => string 'b' (length=1)
      1 => string 'd' (length=1)
  5 => 
    array
      0 => string 'c' (length=1)
      1 => string 'd' (length=1)

要列出数组的所有子集,请使用此组合算法执行

$base =array("a","b","c","d");

for($i = 1; $i<=4 ;$i++){
    $comb = getCombinations($base,$i);

    foreach($comb as $c){
        echo implode(",",$c)."<br />";
    }

}

输出是

a
b
c
d
a,b
a,c
a,d
b,c
b,d
c,d
a,b,c
a,b,d
a,c,d
b,c,d
a,b,c,d

Answer 2

这是一个简单的算法.从1到2 ^{计数(数组)} -1 迭代.在每次迭代时,如果循环计数器的二进制表示中的第j位等于1,则在组合中包括第j个元素.

由于PHP需要能够将2个^{count(数组)}计算为整数,因此可能永远不会超过PHP_INT_MAX.在64位PHP安装中,您的阵列不能超过62个元素,因为2 ⁶²位于下方PHP_INT_MAX而2 ^63位超过它.

编辑:这计算所有可能的组合,而不是排列(即'abc'='cba').它通过以二进制表示原始数组并从0"向上计数"到完整数组的二进制表示来实现,有效地构建了每个可能的唯一组合的列表.

$a = array('a', 'b', 'c', 'd');

$len  = count($a);
$list = array();

for($i = 1; $i < (1 << $len); $i++) {
    $c = '';
    for($j = 0; $j < $len; $j++)
        if($i & (1 << $j))
            $c .= $a[$j];
    $list[] = $c;
}

print_r($list);

Answer 3

这里是：

\n\n

<?php\nfunction combinations($text,$space)\n{\n    // $text is a variable which will contain all the characters/words of which  we want to make all the possible combinations\n    // Let\'s make an array which will contain all the characters\n    $characters=explode(",", $text);\n    $x=count($characters);\n\n    $comb = fact($x);\n\n    // In this loop we will be creating all the possible combinations of the  positions that are there in the array $characters\n\n    for ($y=1; $y<= $comb; $y++)\n    {\n        $ken = $y-1;\n        $f = 1;\n        $a = array();\n        for($iaz=1; $iaz<=$x; $iaz++)\n            {\n                $a[$iaz] = $iaz;\n                $f = $f*$iaz;\n            }\n        for($iaz=1; $iaz<=$x-1; $iaz++)\n            {\n                $f = $f/($x+1-$iaz);\n                $selnum = $iaz+$ken/$f;\n                $temp = $a[$selnum];\n                for($jin=$selnum; $jin>=$iaz+1; $jin--)\n                    {\n                        $a[$jin] = $a[$jin-1];\n                    }\n                $a[$iaz] = $temp;\n                $ken = $ken%$f;\n            }\n        $t=1;\n\n           // Let\xe2\x80\x99s start creating a word combination: we have all the  necessary positions\n        $newtext="";\n\n        // Here is the while loop that creates the word combination\n        while ($t<=$x)\n            {\n                $newtext.=$characters[$a[$t]-1]."$space";\n                $t++;\n            }\n        $combinations[] =  $newtext ;\n    }\n\n        return $combinations;\n\n}\n\nfunction fact($a){\nif ($a==0) return 1;\nelse return $fact = $a * fact($a-1);\n}\n\n$a = combinations("d,f,w,s","");\n    foreach ($a as $v) {\n            echo "$v"."\\n";\n    }\n\n?>\n

\n\n

输出：

\n\n

dfws\ndfsw\ndwfs\ndwsf\ndsfw\ndswf\nfdws\nfdsw\nfwds\nfwsd\nfsdw\nfswd\nwdfs\nwdsf\nwfds\nwfsd\nwsdf\nwsfd\nsdfw\nsdwf\nsfdw\nsfwd\nswdf\nswfd\n

\n\n\n\n

另外，请阅读此内容；

\n