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

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,U,I,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>");