0

我有一组对象。我还有一组必需的对象，包含 0 到 3 个对象。我试图从包含所需对象的初始集中找到 3 个对象的所有组合。

编辑：示例——

objects: {A,B,C,D,E}
required: {A}
output: {A,B,C}, {A,B,D}, {A,B,E}, {A,C,D}, {A,C,E}, {A,D,E}

objects: {A,B,C,D,E}
required: {A,B}
output: {A,B,C}, {A,B,D}, {A,B,E}

明显但缓慢的解决方案类似于：

for(int i = 0; i < objects.size()-2 ; i++){
  for(int j = i; j < objects.size()-1 ; j++){
    for(int k = j; k < objects.size() ; k++){
      if(required.contains(i) || required.contains (j) || required.contains(k)){
        results.add(new Result(i,j,k));
      }
    }
  }
}

该解决方案遍历整个搜索空间，而不考虑所需的对象。

我想出的另一种方法是为每个所需对象的数量编写自定义代码：

switch (required.size()){
case 3:
  results.add(new Result(required));
  break;
case 2:
  Object a = requiredIngredients.toArray()[0];
  Object b = requiredIngredients.toArray()[1];
  for(Object o : objects){
    if(!required.contains(i)){
      results.add(new Result(EnumSet.of(o, a, b)));
    }
  }
  break;

ETC..

这可行，但令人讨厌且不可推广。

第三种方法是制作三个单独的集合，如果存在需求，则缩小集合以仅包含所需的值，然后正常迭代它们：

  for(Object i : firstObjects){
    for(Object j : secondObjects){
      if(i == j) continue;
      for(Object k : thirdObjects){
        if(j == k) continue;
        results.add(new Result(i,j,k));
      }
    }
  }

这似乎更好一些，但会产生重复的组合。例如。它会将 ABC 和 ACB 作为两个单独的结果返回。我可以让结果集识别重复项，但我不想从一开始就计算它。

希望这些例子能说明问题。我觉得有人已经想出了如何解决这类问题，但我很难确定普遍的问题类型。

4

1 回答 1

0

这是一种简单而通用的方法，但可能不是最有效的（在python中）：

from itertools import combinations

def combinations_including(n,objects,required):
  extra=objects-required
  return sorted([sorted(tuple(required)+x) for x in combinations(extra,n-len(required))])

print combinations_including(3,set('ABCDE'),set('A'))
print combinations_including(3,set('ABCDE'),set('AB'))

输出

[['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'B', 'E'], ['A', 'C', 'D'], ['A', 'C', 'E'], ['A', 'D', 'E']]
[['A', 'B', 'C'], ['A', 'B', 'D'], ['A', 'B', 'E']]

如果所需集很小，那么它可能比蛮力更糟糕，但随着所需集的大小增加，它将变得比蛮力更有效。例如，如果所需集与输入集相同，则它会在恒定时间内找到答案。

于 2012-08-30T05:31:55.700 回答