可以创建所有组合以及这些组合的所有组的算法 [英] Algorithm that can create all combinations and all groups of those combinations
问题描述
假设我有一组元素 S = {1，2，3，4，5，6，7，8，9}
我想创建3的组合并将其分组，以使任何数字都不会出现在多个组合中。
I would like to create combinations of 3 and group them in a way such that no number appears in more than one combination.
下面是一个示例：
{{3，7，9}，{1,2,4}，{5， 6，8}}
组中数字的顺序无关紧要，在整个示例中组的顺序也无所谓
The order of the numbers in the groups does not matter, nor does the order of the groups in the entire example.
简而言之，我希望从原始组合的每个可能组合中选择所有可能的组合，但那些要出现在多个组中的数字除外。
In short, I want every possible group combination from every possible combination in the original set, excluding the ones that have a number appearing in multiple groups.
我的问题：就运行时间和内存而言，这实际上可行吗？我的样本量可能在30到50之间。
My question: is this actually feasible in terms of run time and memory? My sample sizes could be somewhere around 30-50 numbers.
如果是这样，创建此算法的最佳方法是什么？最好创建所有可能的组合，然后仅在数字尚未出现时才选择组？
If so, what is the best way to create this algorithm? Would it be best to create all possible combinations, and choose the groups only if the number hasn't already appeared?
我正在Qt 5.6（基于C ++的框架）中编写此代码。
I'm writing this in Qt 5.6, which is a C++ based framework.
推荐答案
您可以递归地执行此操作，并且如果在每个递归中都将第一个元素固定不变，并且仅按值顺序排列3个组，则可以避免重复，例如：
You can do this recursively, and avoid duplicates, if you keep the first element fixed in each recursion, and only make groups of 3 with the values in order, eg:
{1,2,3,4,5,6,7,8,9}
{1,2,3,4,5,6,7,8,9}
将最低元素放在第一个位置（a），并保持在该位置：
Put the lowest element in the first spot (a), and keep it there:
{a，b，c } = {1，*，*}
{a,b,c} = {1, *, *}
对于第二个点（b），从第二个最低值迭代到每个值第二高：
For the second spot (b), iterate over every value from the second-lowest to the second-highest:
{a，b，c} = {1，2〜8，*}
{a,b,c} = {1, 2~8, *}
对于第三点（c），迭代高于第二个值的每个值：
For the third spot (c), iterate over every value higher than the second value:
{1，2〜8，b + 1〜9}
{1, 2~8, b+1~9}
然后递归价值观。
{1,2,3} {4,5,6} {7,8,9}
{1,2,3} {4,5,7} {6,8,9}
{1,2,3} {4,5,8} {6,7,9} < br>
{1,2,3} {4,5,9} {6,7,8}
{1,2,3} {4,6,7} {5 ，8,9}
{1,2,3} {4,6,8} {5,7,9}
{1,2,3} {4， 6,9} {5,7,8}
{1,2,3} {4,7,8} {5,6,9}
{1,2 ，3} {4,7,9} {5,6,8}
{1,2,3} {4,8,9} {5,6,7}
{1,2,4} {3,5,6} {7,8,9}
...
{1,8,9} {2， 6,7} {3,4,5}
{1,2,3} {4,5,6} {7,8,9}
{1,2,3} {4,5,7} {6,8,9}
{1,2,3} {4,5,8} {6,7,9}
{1,2,3} {4,5,9} {6,7,8}
{1,2,3} {4,6,7} {5,8,9}
{1,2,3} {4,6,8} {5,7,9}
{1,2,3} {4,6,9} {5,7,8}
{1,2,3} {4,7,8} {5,6,9}
{1,2,3} {4,7,9} {5,6,8}
{1,2,3} {4,8,9} {5,6,7}
{1,2,4} {3,5,6} {7,8,9}
...
{1,8,9} {2,6,7} {3,4,5}
我说按顺序，那不必是特定顺序（数字，字母...），它可以只是输入的原始顺序。如果您确保将其余所有值按收到顺序传递给下一个递归，则可以避免对每个递归的输入重新排序。
Wen I say "in order", that doesn't have to be any specific order (numerical, alphabetical...), it can just be the original order of the input. You can avoid having to re-sort the input of each recursion if you make sure to pass the rest of the values on to the next recursion in the order you received them.
递归的遍历：
假设您获得了输入{1,2,3,4， 5,6,7,8,9}。作为组中的第一个元素，您从输入中获取第一个元素，对于其他两个元素，您遍历其他值：
Let's say you get the input {1,2,3,4,5,6,7,8,9}. As the first element in the group, you take the first element from the input, and for the other two elements, you iterate over the other values:
{1,2,3}
{1,2,4}
{1,2,5}
{1,2， 6}
{1,2,7}
{1,2,8}
{1,2,9}
{1,3,4}
{1,3,5}
{1,3,6}
...
{1,8,9}
{1,2,3}
{1,2,4}
{1,2,5}
{1,2,6}
{1,2,7}
{1,2,8}
{1,2,9}
{1,3,4}
{1,3,5}
{1,3,6}
...
{1,8,9}
确保第三个元素总是在第二个元素之后，以避免重复：
making sure the third element always comes after the second element, to avoid duplicates like:
{1,3,5}⇆ {1,5,3}
{1,3,5} ⇆ {1,5,3}
现在，让我们说，在某个时候，您已经选择了它作为第一组：
Now, let's say that at a certain point, you've selected this as the first group:
{1,3,7}
{1,3,7}
然后将其余值传递到下一个递归：
You then pass the rest of the values onto the next recursion:
{2,4,5,6,8,9}
{2,4,5,6,8,9}
在此递归中，您将应用与第一组相同的规则：将第一个元素作为组中的第一个元素，然后将其保留在那里，并遍历第二个和第三个元素的其他值：
In this recursion, you apply the same rules as for the first group: take the first element as the first element in the group and keep it there, and iterate over the other values for the second and third element:
{2,4,5}
{2,4,6}
{2,4,8}
{2,4,9}
{2,5， 6}
{2,5,8}
{2,5,9}
{2,6,7}
...
{2,8,9}
{2,4,5}
{2,4,6}
{2,4,8}
{2,4,9}
{2,5,6}
{2,5,8}
{2,5,9}
{2,6,7}
...
{2,8,9}
现在，让我们说在某个时刻，您已将其选为第二组：
Now, let's say that at a certain point, you've selected this as the second group:
{2,5,6}
{2,5,6}
然后将其余值传递到下一个递归：
You then pass the rest of the values onto the next recursion:
{4,8,9}
{4,8,9}
由于这是最后一组，因此只有一种可能性，因此这种特殊的递归将以以下组合结束：
And since this is the last group, there is only one possibility, and so this particular recursion would end in the combination:
{1,3,7} {2,5,6} {4,8,9}
{1,3,7} {2,5,6} {4,8,9}
如您所见，您无需在任何时候对值进行排序，只要您按照对它们的重视程度将它们传递到下一个递归中即可。因此，如果您收到例如：
As you see, you don't have to sort the values at any point, as long as you pass them onto the next recursion in the order you recevied them. So if you receive e.g.:
{q，w，e，r，t，y，u，i，o}
{q,w,e,r,t,y,u,i,o}
，然后从中选择组：
{q，r，u}
{q,r,u}
然后您应该继续传递：
{w，e，t，y，i，o}
{w,e,t,y,i,o}
下面是一个演示该方法的JavaScript代码段；
（过滤器函数创建输入数组的副本，其中删除了元素0，i和j。）
function clone2D(array) {
var clone = [];
for (var i = 0; i < array.length; i++) clone.push(array[i].slice());
return clone;
}
function groupThree(input) {
var result = [], combination = [];
group(input, 0);
return result;
function group(input, step) {
combination[step] = [input[0]];
for (var i = 1; i < input.length - 1; i++) {
combination[step][1] = input[i];
for (var j = i + 1; j < input.length; j++) {
combination[step][2] = input[j];
if (input.length > 3) {
var rest = input.filter(function(elem, index) {
return index && index != i && index != j;
});
group(rest, step + 1);
}
else result.push(clone2D(combination));
}
}
}
}
var result = groupThree([1,2,3,4,5,6,7,8,9]);
for (var r in result) document.write(JSON.stringify(result[r]) + "<br>");
这篇关于可以创建所有组合以及这些组合的所有组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
