0

例如，如果和A={0,1,2,3,4}，结果将是：r=3B={1,4}

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

这就是 A 的所有 r-long 组合，不包括[0, 2, 3]，因为它既不包含 1 也不包含 4。

我目前拥有的解决方案如下，使用最快的算法来获取我所知道的正常组合，并且只是做一个简单的检查以查看生成的组合是否还包含 B （java）的元素：

    int[] A = new int[]{0,1,2,3,4};
    int[] B = new int[]{1,4};
    int n = A.length;
    int r = 3;

    int[] picks = new int[r]; //Holds indexes of elements in A
    for (int i = 0; i < picks.length; i++)
        picks[i] = i;

    int lastindex = picks.length - 1;

    outer:
    while (true) {
        int at = lastindex;
        while (true) {
            picks[at] += 1;
            if (picks[at] < n) {
                int displacement = picks[at] - at; // at + displacement = picks[at], at + displacement + 1 = picks[at] + 1 ,...

                // Make all picks elements after at y = picks[at] + x, so picks={0, 2, 4, 6, 18, 30} & at=3 --> picks={0, 2, 4, 5, 6, 7}
                // (Note that this example will never take place in reality, because the 18 or the 30 would be increased instead, depending on what n is)

                // Do the last one first, because that one is going to be the biggest,
                picks[lastindex] = lastindex + displacement;
                if (picks[lastindex] < n) { // and check if it doesn't overflow
                    for (int i = at + 1; i < lastindex; i++)
                        picks[i] = i + displacement;

                    int[] combination = new int[r];
                    for (int i = 0; i < r; i++)
                        combination[i] = A[picks[i]];
                    System.out.print(Arrays.toString(combination));
                    //^With this, all r-long combinations of A get printed

                    //Straightforward, bruteforce-ish way of checking if int[] combination
                    //contains any element from B
                    presence:
                    for (int p : combination) {
                        for (int b : B) {
                            if (p==b) {
                                System.out.print(" <-- Also contains an element from B");
                                break presence;
                            }
                        }
                    }

                    System.out.println();

                    break;
                }
            }
            at--;
            if (at < 0) {
                //Moving this check to the start of the while loop will make this natively support pick 0 cases (5C0 for example),
                //but reduce performance by I believe quite a bit. Probably better to special-case those (I haven't
                // done that in this test tho)
                break outer;
            }
        }
    }

输出：

[0, 1, 3] <-- Also contains an element from B
[0, 1, 4] <-- Also contains an element from B
[0, 2, 3]
[0, 2, 4] <-- Also contains an element from B
[0, 3, 4] <-- Also contains an element from B
[1, 2, 3] <-- Also contains an element from B
[1, 2, 4] <-- Also contains an element from B
[1, 3, 4] <-- Also contains an element from B
[2, 3, 4] <-- Also contains an element from B

正如评论中所写，我相信这种方法非常初级。谁能想到一个更快的方法来做到这一点？

4

1 回答 1

1

假设您有一个int[][] FindCombinations(int[] set, int length)返回所有length-long 组合列表的函数set，请执行以下操作（伪代码）：

for i=1 to B.length
{
  int bi = B[i];

  A = A - bi; // remove bi from A
  foreach C in FindCombinations(A, r-1)
  {
     output C+bi // output the union of C and {bi}
  }
}

这样，所有组合都至少包含 B 中的一个元素（也可能包含 B 中尚未使用的元素），而无需太多额外的工作。所有其他组合都被免费消除（根本不必找到），并且组合包含每个组合的 B 元素的测试也被消除。

该算法是否更快，很大程度上取决于您从集合中添加/删除元素的效率以及包含与排除组合的百分比（即，如果您最终只排除了总组合的 1%，则可能不值得）

请注意，当使组合与 {b[i]} 联合时，它们还可能包含元素 B[j]，其中 j>i。当你得到与 B[j] 联合的组合时，它们都不会包含 B[i]，所以所有组合都是唯一的。

于 2017-04-27T21:56:25.053 回答