是否有一种算法可以输出两组元素的所有可能组合？ [英] Is there an algorithm to output all possible combinations of two sets of elements?

问题描述

我正在用PHP编写一个应用程序，用户可以输入两组信息并打印出两组的所有可能组合。目的是通过练习不同的问答方式，将其用作学习语言的教学工具。

I am writing an application in PHP where users can enter two sets of information and have every possible combination of the two sets printed out. The goal is to use it as a teaching tool for learning language by practicing different patterns of a question and answer.

例如，我们可能会练习您是否尝试过...？这个问题。加上蹦极，跳帆，跳伞和水肺潜水四项活动之一。还有四个可能的答案：

For example, we may practice the question "Have you ever tried...?" plus one of four activities, such as bungee jumping, para sailing, skydiving, and scuba diving. There would also be four possible answers:

1. 是的，我很喜欢。


2. 是的，我有，但我不喜欢它。


3. 否，我没有，但是我想尝试一下。


4. 否，我没有't，我不想尝试。

1. Yes I have, and I enjoyed it.
2. Yes I have, but I didn't like it.
3. No I haven't, but I want to try it.
4. No I haven't, and I don't want to try it.

用户将输入两组数据，应用程序将然后打印包含所有可能的问题和答案组合的卡片。例如，卡1看起来像这样：

The user would input the two sets of data, and the application would then print sheets of cards containing all possible combinations of the questions and answers. For example, card 1 would look like this:

1. 高空跳伞：是的，我很喜欢。


2. 水肺潜水：是的，但是我不喜欢。


3. 帆伞运动：不，我没有，但是我想尝试。


4. 蹦极跳：不，我没有，我也不想尝试。

1. skydiving: Yes I have, and I enjoyed it.
2. scuba diving: Yes I have, but I didn't like it.
3. parasailing: No I haven't, but I want to try it.
4. bungee jumping: No I haven't, and I don't want to try it.

下一个卡可能看起来像这样：

The next card might then look like this:

1. 高空跳伞：是的，但我不喜欢它。


2. 水肺潜水：不，我没有，但是我想尝试。


3. 帆伞运动：不，我没有，我也不想尝试。


4. 蹦极跳：是的，我喜欢它。

1. skydiving: Yes I have, but I didn't like it.
2. scuba diving: No I haven't, but I want to try it.
3. parasailing: No I haven't, and I don't want to try it.
4. bungee jumping: Yes I have, and I liked it.

所以您可以看到，有许多不同的可能组合。想法是两个列表的长度相同，以允许打印所有可能性。同样重要的是，任何一张卡片上的问题或答案都不会被多次使用，并且两张卡片可以相同。最好的方法是什么？实际的输入和输出不是问题，我之前做过类似的事情。我只需要算法来产生组合。

So as you can see, there are many different possible combinations. The idea would be that both lists would be of the same length to allow all of the possibilities to be printed out. It is also important that no question or answer gets used more than once on any card, and that two cards can be alike. What would be the best way to go about this? The actual input and output is not the problem--I've done similar things before. I just need the algorithm to produce the combinations.

编辑：我想我真正想要的是使每张卡的活动保持相同的顺序，但是答案的所有可能组合。因此，我真正需要的是能够产生以下一组索引，以便从答案数组中获取数据。所以我真的想要更多这样的东西：

I guess what I'm really after is to keep the activities in the same order for each card, but have every possible combinations of answers. So what I really need is to be able to produce the following set of indexes for getting data out of the answers array. So I really want something more like this:

• 0,1,2,3


• 0 ，1,3,2


• 0,2,1,3


• 0,2,3,1


• 0,3,1,2


• 0,3,2,1


• 1,0,2,3


• 1,0,3,2


• 1,2,0,3


• 1,2,3,0

• 0,1,2,3
• 0,1,3,2
• 0,2,1,3
• 0,2,3,1
• 0,3,1,2
• 0,3,2,1
• 1,0,2,3
• 1,0,3,2
• 1,2,0,3
• 1,2,3,0

...等等，直到产生所有可能的组合为止。

...and so on until all possible combinations have been produced.

推荐答案

好的，有了新的标准，我想我会更好一些。

OK, with the new criteria, I think I understand a little better.

尝试递归。我的解决方案很混乱，但是我可以带您逐步解决：

Try recursion. My solution is messy as hell but I can walk you through it:

$activities = array('a', 'b', 'c', 'd'); // Input all your activities as elements here.
$responses = array(1, 2, 3, 4); // Input all your responses as elements here.

// Recursive function outputCombos accepts both arrays (for eventual output).
// $workingArray is the array of the current branch we're working with.
function outputCombos ($activities, $responses, $workingArray) {
    // Once the working array has been loaded to the maximum amt, print everything out.
    if (count($workingArray) == count($responses)) {
        echo "Combo\n";
        for ($x = 0; $x < count($activities); $x++) {
            echo $activities[$x].'::'.$workingArray[$x]."\n";
        }
    // If the working array isn't full, add an element that isn't currently in the working array, and recursively run the function again.
    } else {
        foreach ($responses as $response) {
            // Iterate through list of all possible responses, add it into a new working array and run the function if the response hasn't been used in this working array.
            if (!in_array($response, $workingArray)) {
                $newArray = $workingArray;
                $newArray[] = $response;
                outputCombos($activities, $responses, $newArray);
            }
        }
    }
}

foreach ($responses as $response) {
    echo '<pre>';
    // Start each branch of tree with unique response (should be 4 in this case).
    outputCombos($activities, $responses, array($response));
    echo '</pre>';
}

这篇关于是否有一种算法可以输出两组元素的所有可能组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！