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));
      }
    }
  }
}

このソリューションは、必要なオブジェクトに関係なく、検索スペース全体をトラバースします。

私が思いついたもう1つのアプローチは、必要なオブジェクトの数ごとにカスタムコードを作成することでした。

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;

等..

これは機能しますが、不快で一般化できません。

3番目のアプローチは、3つの別々のセットを作成し、要件が存在する場合は必要な値のみを含むようにセットを縮小してから、通常どおりそれらを反復処理することです。

  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の両方を2つの別々の結果として返します。結果セットに重複を認識させることもできますが、最初から計算したくないのです。

うまくいけば、これらの例が問題を明らかにします。誰かがこの種の問題を解決する方法をすでに理解しているように感じますが、私は一般化された問題の種類を特定するのに苦労しています。

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 に答える