查找数组值的每个可能的排列


Find every possible permutation of array values

情况:有 5 个问题,有多个可能的答案。其中四个问题可以有一个答案,一个问题有一个或多个答案。任何问题都可能没有答案。

我想找出这些答案的每一个可能的组合。

我认为这不是重复的,因为它处理单个字符或数字的可能排列。


我相信这个例子会生成大约 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"
    )
);

我希望我回答了你的问题,并且这个答案似乎对你有帮助......

初始条件

除了您的示例之外,让我们介绍第二个数组,其中包含有关哪些问题可能有多个答案的信息:

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