从给定数量的元素获得阵列的所有独特组合

Question

我想要一种方法来获得给定数组长度的所有给定数字的所有组合。 在我的项目中，数组大小通常为7.因此，我编写了一个像这样的测试代码，以查看是否可以获得所有需要的组合。最重要的部分是每个结果数组必须是唯一的，最大的数组大小必须是7

<?php 
$numbers = [1, 2, 3, 4, 5, 6, 7]; 

$arraysize = 7; 

$subset = []; 
$count = count($numbers); 
for ($i = 0; $i < $count; $i++) { 
    $subset[] = $numbers[$i]; 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     $subset[] = $numbers[$i] . $numbers[$j]; 
    } 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     for ($k=$j; $k < $count; $k++) { 
      $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k]; 
     } 
    } 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     for ($k=$j; $k < $count; $k++) { 
      for ($l=$k; $l < $count; $l++) { 
       $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l]; 
      } 
     } 
    } 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     for ($k=$j; $k < $count; $k++) { 
      for ($l=$k; $l < $count; $l++) { 
       for ($m=$l; $m < $count; $m++) { 
        $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m]; 
       } 
      } 
     } 
    } 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     for ($k=$j; $k < $count; $k++) { 
      for ($l=$k; $l < $count; $l++) { 
       for ($m=$l; $m < $count; $m++) { 
        for ($n=$m; $n < $count; $n++) { 
         $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m] . $numbers[$n]; 
        } 
       } 
      } 
     } 
    } 
} 

for ($i=0; $i < $count; $i++) { 
    for ($j=$i; $j < $count; $j++) { 
     for ($k=$j; $k < $count; $k++) { 
      for ($l=$k; $l < $count; $l++) { 
       for ($m=$l; $m < $count; $m++) { 
        for ($n=$m; $n < $count; $n++) { 
         for ($o=$n; $o < $count; $o++) { 
          $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l] . $numbers[$m] . $numbers[$n] . $numbers[$o]; 
         } 
        } 
       } 
      } 
     } 
    } 
} 

echo "<pre>"; 
print_r($subset); 
echo "</pre>"; 
?> 

当我运行这段代码，我得到了类似的组合，我想（我做组合为字符串清楚地看到结果，但通常每个结果项在$subset数组必须是数组） 使用此代码，我可以得到所有独特的组合。

但正如你所看到的，这段代码很难看。我试图让这个递归函数，但我失败了。任何人都可以指出我正确的方向来获得像这样的完全相同的结果吗？ （在$subset阵列的每个项目通常必须是包含数字数组）

Answer 1

我终于找到了一种方法来添加递归函数从给定的数字创造独特的组合：

$numbers = [1, 2, 3, 4, 5, 6, 7]; 

function subsetSumRecursive($numbers, $arraySize, $level = 1, $i = 0, $addThis = []) 
{ 
    // If this is the last layer, use a different method to pass the number. 
    if ($level == $arraySize) { 
     $result = []; 
     for (; $i < count($numbers); $i++) { 
      $result[] = array_merge($addThis, array($numbers[$i])); 
     } 
     return $result; 
    } 

    $result = []; 
    $nextLevel = $level + 1; 
    for (; $i < count($numbers); $i++) { 
     // Add the data given from upper level to current iterated number and pass 
     // the new data to a deeper level. 
     $newAdd = array_merge($addThis, array($numbers[$i])); 
     $temp = subsetSumRecursive($numbers, $arraySize, $nextLevel, $i, $newAdd); 
     $result = array_merge($result, $temp); 
    } 

    return $result; 
} 

echo "<pre>"; 
print_r(subsetSumRecursive($numbers, 7)); 
echo "</pre>"; 

---

Answer 2

可以简化这一逻辑（和使代码不太难看），而无需使用去递归：

for ($i = 0; $i < $count; $i++) { 
    $subset[] = $numbers[$i]; 
    for ($j=$i; $j < $count; $j++) { 
     $subset[] = $numbers[$i] . $numbers[$j]; 
     for ($k=$j; $k < $count; $k++) { 
      $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k]; 
      for ($l=$k; $l < $count; $l++) { 
       $subset[] = $numbers[$i] . $numbers[$j] . $numbers[$k] . $numbers[$l]; 
      } 
     } 
    } 
} 

Answer 3

下面将在所有情况下工作，即使你有重复号码数组中

$array = array(1,2,3,4,5,6,7,8,9,10,11,12,13,14); 
sort($array); //in case it 's not sorted 
$array = array_slice($array,-7); 
$num = count($array); 
    $total = pow(2, $num); 
    $result= array(); 
    $element=''; 
    for ($i = 0; $i < $total; $i++) 
    {  

      for ($j = 0; $j < $num; $j++) 
       {     
       if (pow(2, $j) & $i) 
       { 
       $element=$element.$array [$j];     
       }          
       } 
       $result[]=$element; 
       $element=''; 
     } 
     print_r($result); 

Answer 4

此实现返回的所有项目（7项7 = 823542组合）的所有组合：

function combine_all(array $numbers) { 
    $count = count($numbers); 

    $result = array_map('strval', $numbers); 
    for($i = 1; $i < $count; ++$i) { 
     $combinations = array_slice($result, pow($count, $i-1)); 
     foreach($numbers as $number) { 
      foreach($combinations as $combination) { 
       $result[] = $number . ',' . $combination; 
      } 
     } 
    } 

    return $result; 
} 

当使用的print_r到输出的数据，它可以执行非常缓慢：

$array = array_fill(0, pow(7,7), ''); 
$t = microtime(true); 
echo '<pre>'; 
print_r($array); 
echo '</pre>'; 
echo microtime(true) - $t; 
// 0.75329303741455 


$t = microtime(true); 
echo '<pre>'; 
print_r(combine_all(array(1,2,3,4,5,6,7))); 
echo '</pre>'; 
echo microtime(true) - $t; 
// 1.7037351131439 


$t = microtime(true); 
combine_all(array(1,2,3,4,5,6,7)); 
echo microtime(true) - $t; 
//0.75869607925415 

要限制的项目数量，使用array_slice功能：

combine_all(array_slice($numbers, 0, 7)); 

如果你真的想要一个递归函数，你可以做这样的事情：

function combine_all(array $numbers, $cnt=null, $baseCombination=null) { 
    if($baseCombination === null) { 
     $cnt = count($numbers); 
    } 

    if($cnt > 0) { 
     $result = array(); 
     foreach($numbers as $number) { 
      $combination = $number . ',' . $baseCombination; 
      $result[] = $combination; 
      $result = array_merge($result, combine_all($numbers, $cnt-1, $combination)); 
     } 
     return $result; 
    } 

    return array(); 
} 

但it takes too much memory。