6

{1,1,1,2,2,3,3,3} などのアイテムのセットと、{{3},{1,2},{1 などの制限セットがあります。 ,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. アイテムの順列を探していますが、最初の要素は 3 でなければならず、2 番目の要素は 1 または 2 でなければなりません。

適合するそのような順列の 1 つ: {3,1,1,1,2,2,3}

一般に、この問題のすべての順列をカウントするアルゴリズムはありますか? このタイプの問題に名前はありますか?

説明のために、特定のタイプの「制限セット」についてこの問題を解決する方法を知っています。アイテムのセット: {1,1,2,2,3}、制限 {{1,2}、{1,2,3}、{1,2,3}、{1,2}、{1,2 }}。これは 2!/(2-1)!/1! に等しいです。* 4!/2!/2!. 最初に 3 つを効果的に並べ替えます。これは最も制限が厳しいためです。次に、余裕のある残りのアイテムを並べ替えます。

また...多項式時間。それは可能ですか？

更新: これについては、以下のリンクで詳しく説明します。上記の問題は「完全一致のカウント」と呼ばれ、上記の各順列制限は、占有者に対するスロットのマトリックス上の {0,1} で表されます。

4

4 に答える 4

1

ここでの他のすべての解決策は、指数関数的な時間です-必要がない場合でも。この問題は同様の下部構造を示すため、動的計画法で解決する必要があります。

あなたがしたいのは、サブ問題の解決策を記憶するクラスを書くことです：

class Counter {
  struct Problem {
     unordered_multiset<int> s;
     vector<unordered_set<int>> v;
  };

  int Count(Problem const& p) {
    if (m.v.size() == 0)
      return 1;
    if (m.find(p) != m.end())
      return m[p];
    // otherwise, attack the problem choosing either choosing an index 'i' (notes below)
    // or a number 'n'.  This code only illustrates choosing an index 'i'.
    Problem smaller_p = p;
    smaller_p.v.erase(v.begin() + i);
    int retval = 0;
    for (auto it = p.s.begin(); it != p.s.end(); ++it) {
      if (smaller_p.s.find(*it) == smaller_p.s.end())
        continue;
      smaller_p.s.erase(*it);
      retval += Count(smaller_p);
      smaller_p.s.insert(*it);      
    }
    m[p] = retval;
    return retval;
  }

  unordered_map<Problem, int> m;
};

このコードは、v [i] .size（）が小さい場所で選択する必要があるインデックスiの選択を示しています。もう1つのオプションは、番号nを選択することです。これは、配置できる場所vがほとんどない番号nである必要があります。2つの決定要因のうち最小のものが勝つはずです。

また、Problemのハッシュ関数を定義する必要があります。これは、boostのハッシュ関数を使用してそれほど難しくないはずです。

このソリューションは、ベクトルをset <>に置き換え、unordered_setの<演算子を定義することで改善できます。これにより、さらに多くの同一のサブ問題が1つのマップ要素にまとめられ、指数関数的な爆発がさらに軽減されます。

このソリューションは、番号が同じ値にハッシュされて比較され、同じであると比較されることを除いて、同じ問題インスタンスを作成することによってさらに改善できます。

于 2010-05-08T01:01:23.540 に答える
1

あなたは木を建てることができます。レベル0：ルートノードを作成します。レベル1：ルートの子として最初の「制限セット」の各アイテムを追加します。レベル2：各レベル1ノードの子として、2番目の制限セットの各アイテムを追加します。レベル3：各レベル2ノードの子として、3番目の制限セットの各アイテムを追加します。..。

順列カウントは、最終ツリーのリーフノードの数になります。

編集

「アイテムのセット」{1,1,1,2,2,3,3,3}が何を意味するのかは不明です。各値を使用できる回数を制限する場合（「1」は3回、「2」は2回など）、もう1つの手順が必要です。

  • ツリーにノードを追加する前に、アイテムのセットから現在のパスで使用されている値を削除します。追加する値がまだ使用可能な場合（たとえば、「1」を追加したいが、「1」はこれまでに2回しか使用されていない）、ツリーに追加します。
于 2010-05-07T17:38:24.937 に答える
1

数字のプールを使用する再帰的なソリューションを検討することができます (提供する例では、{1,1,1,2,2,3,3,3} に初期化されます)、指定されたインデックスで決定しますパラメータとして、このインデックスに配置する桁を指定します (もちろん、指定した制限を使用します)。

必要に応じて、疑似コードを提供できます。

于 2010-05-07T17:07:03.360 に答える
0

スペースを節約するために、ツリーの代わりに有向グラフを作成できます。

  • ルート ノードを作成します。
  • 最初のセットの各アイテムのノードを作成し、ルートから新しいノードにリンクします。
  • 2 番目のセットのアイテムごとにノードを作成し、最初のセットの各アイテムから 2 番目のセットのアイテムにリンクします。
  • ...

順列の数は、ルート ノードから最終セットのノードへのパスの数です。

于 2010-05-07T17:44:18.433 に答える