可以创建所有组合和这些组合的所有组的算法

Question

假设我有一组元素S = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

我想创建3的组合，并以一种方式将它们分组，使数字不会出现在多个组合中。

下面是一个例子:{ {3, 7, 9}, {1, 2, 4}, {5, 6, 8} }

组中数字的顺序不重要，整个例子中组的顺序也不重要。

简而言之，我想要原始集合中所有可能组合中的所有可能组合，不包括在多个组中出现一个数字的组合。

我的问题是:这在运行时间和内存方面实际上是可行的吗?我的样本量可能在30-50个数字之间。

如果是，创建该算法的最佳方法是什么?最好是创建所有可能的组合，并只在数字尚未出现时选择组吗?

我在Qt 5.6中写这个，这是一个基于c++的框架。

Answer 1

您可以递归地做到这一点，并避免重复，如果您在每次递归中保持第一个元素固定，并且仅按顺序将值分成3组，例如:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

把最低的元素放在第一个位置(a)，并保持在那里:

{a,b,c} = {1， *， *}

对于第二个点(b)，遍历从第二低到第二高的每个值:

{a,b,c} = {1,2 ~8， *}

对于第三个位置(c)，遍历每个比第二个值高的值:

{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}
{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}
{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, 3, 5} ⇆{1、5、3}

现在，假设在某一点上，你选择了这个作为第一组:

{1、3、7}

然后将其余的值传递给下一个递归:

{2、4、5、6、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}

现在，假设在某一点上，你选择了这个作为第二组:

{2、5、6}

然后将其余的值传递给下一个递归:

{4 8 9}

因为这是最后一组，所以只有一种可能，所以这个特殊的递归将以组合结束:

{1,3,7} {2,5,6} {4,8,9}

如您所见，您不必在任何地方对值进行排序，只要按照您收到它们的顺序将它们传递给下一个递归即可。所以如果你收到例如:

{q、w e r t y,你,我,o}

，你从这个组中选择:

{q, r u}

那么你应该传递:

{w e t y, i, o}

---

下面是演示该方法的JavaScript片段;它返回一个包含元素组组合的3D数组。
(过滤器函数创建一个输入数组的副本，删除元素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>");

Answer 2

对于一次取3个n个东西，可以使用3个嵌套循环:

    for(k = 0; k < n-2; k++){
        for(j = k+1; j < n-1; j++){
            for(i = j+1; i < n  ; i++){
                ...  S[k] ... S[j] ... S[i]
            }
        }
    }

对于一次取k个值的n个事物的一般解，您可以使用包含k个计数器的数组。

Answer 3

我认为你可以通过使用动态规划的硬币变化问题来解决它，只要假设你正在寻找3的变化，数组中的每个索引都是硬币值1，然后只输出已经找到的硬币(数组中的值)。链接:https://www.youtube.com/watch?v=18NVyOI_690