順列までのサブセットのコレクションを比較すると、

Question

私は、配列[i]の[j]を持っています。要素がセットのサブセットとして解釈、CHARは{1、...、8}（k番目のビットが1である場合、要素kは、サブセットです）。私はそれが関連しているとは思いませんが、すべての要素が正確に4ビットが設定されています。

すべての行は、[1]〜[J] .. [N] [j]は{1、...、8}の部分集合の集合です。私は1つが、の順列によって他から得ることができる場合、2つの行が重複して考慮される重複する行を削除する必要が{1、...、8}。

例（0bxxxxxxxxは2進数を意味する）：

0b11000000, 0b01100000, 0b00110000

タグの複製であります

0b00110000, 0b00011000, 0b00100100

前者は順列を適用することによって後者から得ることができるので

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6

と結果の並べ替え。

は、パフォーマンスの考慮事項については、アレイは、それぞれ最大20個の要素で含む、約2000行を含みます。これが役立つ可能性がある場合、各行は、すでに発注され、また、行は辞書昇順です。 C溶液が好ましいであろうように、アルゴリズムの残りは、Cで書かれている。

ご協力いただきありがとうございます。

Answer 1

すべてのサブセットは、2つの要素を持っていた場合、

、これはサブセットと、グラフ同型を表すであろうグラフの辺を表します。 これは（したがって、おそらく難しい）、より一般的であるので、私はグラフ同型を解決し、彼らはここに適用するかどうかを確認するために使用ヒューリスティックを見て思います。

安く同型を除外することができ、グラフ同型ヒューリスティックがたくさんあります。特定のコレクションでは、各要素は、そのをソートする属さないどのように多くのサブセットを計算することができます。あなたの例では、両方のコレクションは、[2,2,1,1,0,0,0,0]になるだろう。 2つのコレクションのためのソート順序が異なる場合、何の同型はありません。もちろん、平等であることを保証するものではありません。

非同型のグラフをふるいにかける時にも優れている（そしておそらくここで適用することもできる）より多くの同様の経験則があります。

また、8！唯一の40320ですので、ブルート強制的にすべての順列は完全に実現不可能ではありません。