查找數組值的每個可能的排列組合

Question

情況：有5個問題有多個可能的答案。四個問題可以有一個或多個答案的答案。任何問題都無法回答。

我想制定出這些答案的每一個可能的組合。

我認爲這不是this的重複，因爲它涉及單個字符或數字的可能排列。

---

我相信這個例子會產生像230,400種可能的排列

$questions = array(
    "q1" => array(
     "1a", 
     "1b", 
     "1c" 
    ), 
    "q2" => array(
     "2a", 
     "2b", 
     "2c", 
     "2d" 
    ), 
    "q3" => array(
     "3a", 
     "3b", 
     "3c" 
    ), 
    "q4" => array(// this question can have any number of these answers selected, or none 
     "4a", 
     "4b", 
     "4c", 
     "4d", 
     "4e", 
     "4f" 
    ), 
    "q5" => array(
     "5a", 
     "5b", 
     "5c" 
    ) 
); 

Answer 1

我希望我有你的問題的權利，而這答案似乎對你有幫助...

初始條件

除了你的例子，我們來介紹第二個數組，其中包含哪些問題可能有多個答案：

$multi_questions = array('q4'); 

這將告訴我們的算法在下面描述的問題4可能有任何數量的答案選擇，而所有問題可能只有一個答案或根本沒有答案。

的答案

的集合中選擇用於特定問題的答案的可能的組合數是獨立於任何其他問題。對於總數爲n可能的答案和最多1個選定答案的問題，該問題可能的選擇數量爲n+1。如果問題允許選擇多個答案，則有2^n這個問題的可能組合（每個答案有兩個選項：選擇或不選擇）。

在您的示例中，這會導致所選答案的可能組合總數爲4 * 5 * 4 * 2^6 * 4 = 20480。這個數字可以計算就像如下：

$combinations = 1; 
foreach ($questions as $q => $answers) 
{ 
    if (in_array($q, $multi_questions)) 
     $combinations *= 1 << count($answers); 
    else 
     $combinations *= count($answers) + 1; 
} 

遍歷答案

的所有可能的組合，如果你不僅是在回答的組合的數量感興趣，但要產生所有這些，你可以使用算法如下。對於具有多個可能答案的問題，它將以二進制數形式給出的一組答案進行編碼。這意味着，號碼001010將代表答案集['4c','4e']。

$q_keys = array_keys($questions); 

// Start with no answer selected for any question 
$answer_set = array(); 
$q_max = array(); 
for ($i = 0; $i < count($q_keys); $i++) 
{ 
    $answer_set[$i] = 0; 
    $q_max[$i] = (in_array($q_keys[$i], $multi_questions)) 
       ? (1 << count($questions[$q_keys[$i]])) - 1 
       : count($questions[$q_keys[$i]]); 
} 

// Iterate over all combinations of answers 
while ($answer_set[0] <= $q_max[0]) 
{ 

    // Decode answer set to array of selected answers for each question 
    $answers = array(); 
    for ($i = 0; $i < count($q_keys); $i++) 
    { 
     if (in_array($q_keys[$i], $multi_questions)) 
     { 
      $answers[$q_keys[$i]] = array(); 
      for ($a = 0; $a < count($questions[$q_keys[$i]]); $a++) 
       if (($answer_set[$i] & (1 << $a)) != 0) // Is the bit corresponding to answer no. $a set? 
        $answers[$q_keys[$i]][] = $questions[$q_keys[$i]][$a]; 
     } 
     else 
      $answers[$q_keys[$i]] = ($answer_set[$i] > 0) 
            ? array($questions[$q_keys[$i]][$answer_set[$i] - 1]) 
            : array(); // Encode no answer as empty array 
    } 

    // Do something with the array of answers for each question ($answers) 
    // ... 

    // Forward the answer set 
    for ($i = count($q_keys) - 1; $i >= 0; $i--) 
    { 
     if (++$answer_set[$i] > $q_max[$i] && $i > 0) 
      $answer_set[$i] = 0; 
     else 
      break; 
    } 

}