追加の制限付きでランダムなマルチセット順列を効果的に生成する方法として既知のアルゴリズムはありますか？
例：次のような複数のアイテムのセットと、 {、、、、、、、}の{1,1,1,2,2,3,3,3}ような制限セットのセットがあります。アイテムの順列を探していますが、最初の要素は3で、2番目の要素は1または2である必要があります。{3}{1,2}{1,2,3}{1,2,3}{1,2,3}{1,2,3}{2,3}{2,3}
制限に適合するそのような順列の1つは次のとおりです。{3,1,1,1,2,2,3,3}
はいあります。このドイツ語フォーラムで質問したところ、次の回答が得られました。問題は、二部グラフで最大の一致を見つけることに還元できます。これを行うには、マルチセット内のすべての要素に頂点を導入します。これらの頂点は、二部グラフの片側を形成します。次に、各制限セットの頂点を導入します。これらの頂点は、二部グラフの反対側を形成します。ここで、接続されたセットに含まれる要素を表す場合にのみ、最初の側の頂点が「ヒット」するように、各制限セットから最初の側の頂点にエッジを導入します。
この例の二部グラフは次のようになります。
マッチングでは、隣接する 2 つのエッジが選択されないようにエッジが選択されます。たとえば、最初の "1" が 2 番目の制限 "{1,2}" に選択された場合、この頂点から別のエッジを使用すると一致する結果が得られなくなるため、他の制限には使用できなくなります。 .
これについて別の質問がある場合は、お気軽にお尋ねください。