從給定數量的元素獲得陣列的所有獨特組合

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。