-1

Situation: there are 5 questions with multiple possible answers. Four of the questions can have a single answer with one having one or more answers. Any of the questions could have no answer.

I want to work out each and every possible combination of these answers.

I think this isn't a duplicate of this as it deals with possible permutations of single characters or numbers.

I believe this example would generate something like 230,400 possible permutations

$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"
    )
);
Community
  • 1
  • 1
Garry Welding
  • 3,599
  • 1
  • 29
  • 46
  • Why do you need PHP for this task if it is fixed? If it isn't, what are the variables? – Callidior Mar 15 '16 at 14:23
  • Doesn't need to be PHP, could be Python or whatever. However, the number of questions and answers is dynamic, so it isn't fixed. – Garry Welding Mar 15 '16 at 14:24
  • Okay, but besides the comment, the array representation you've given contains no clue on whether a specific question may have only one or multiple answers. This is a necessary information for computing the total number of possible answer combinations. Are you interested in that number or do you need all possible combinations themselves? – Callidior Mar 15 '16 at 14:26
  • read the entire question, 4 of the questions can have only 1 answer, and one of the questions can have any number of the answers, ALL of the questions can have NO answer potentially. I've even highlighted in the example array which question is the one that can have multiple answers. – Garry Welding Mar 15 '16 at 14:29
  • Yes, but in the previous comment you say, the number of questions is dynamic. So, is it always the fourth question that can have multiple answers? – Callidior Mar 15 '16 at 14:30
  • No, any question could have multiple answers, and any solution should be able to account for this. However, if I can get a solution to work on the example given above then I can modify it to deal with that situation. – Garry Welding Mar 15 '16 at 14:33
  • Is the order of answers important? Since you're talking about "permutations", is `['3a','4e']` different from `['4e','3a']`? – Callidior Mar 15 '16 at 15:03
  • I would say that the order is not important no. – Garry Welding Mar 15 '16 at 15:06
  • There are quite a few answers around combinations and permutations on SO already http://stackoverflow.com/questions/1679605/combinations-dispositions-and-permutations-in-php – Josh J Mar 15 '16 at 15:48
  • Again, these give all possible combinations of n number of characters or numbers, not really what I'm looking for. – Garry Welding Mar 15 '16 at 15:49
  • I don't understand, what you mean by saying"permutation", because this is what a permutation means to me: https://en.wikipedia.org/wiki/Permutation – ead Mar 15 '16 at 23:00

1 Answers1

0

I hope I've got your question right and that this answer seems helpful to you...

Initial conditions

In addition to your example, let's introduce a second array with information about which question(s) may have multiple answers:

$multi_questions = array('q4');

This would tell our algorithm described in the following that question 4 may have any number of answers selected, while all over questions may only have a single or no answer at all.

Number of possible combinations of answers

The set of answers selected for a specific question is independent from any other question. For a question with a total number of n possible answers and maximum of 1 selected answer, the number of possible selections for that question is n+1. If the question allows the selection of multiple answers, there are 2^n possible combinations for that question (each answer has two options: chosen or not chosen).

In your example, this leads to a total number of 4 * 5 * 4 * 2^6 * 4 = 20480 possible combinations of selected answers. This number can be computed like follows:

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

Iterating over all possible combinations of answers

If you are not only interested in the number of answer combinations, but want to generate them all, you can use an algorithm like the following. For the questions with more than one possible answer, it encodes the set of answers given as binary number. That means, the number 001010 would represent the answer set ['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;
    }

}
Callidior
  • 2,899
  • 2
  • 18
  • 28