サブセットの集合と順列の比較

Question

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

各行a [1] [j] .. a [n] [j]は、{1、...、8}のサブセットの集合です。 2つの行が{1、...、8}の順列によって他方から取得できる場合、重複行と見なされる重複行を削除する必要があります。

例（0bxxxxxxxxは2進数を意味する）：前者は置換

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

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

0b11000000, 0b01100000, 0b00110000 

は

0b00110000, 0b00011000, 0b00100100 

の複製であります結果を並べ替える。

パフォーマンス上の理由から、配列には約2000個の行が含まれ、それぞれに最大20個の要素が含まれています。各行はすでに順序付けされており、行が辞書順に昇順になっています（これが役立つ場合）。アルゴリズムの残りの部分はCで書かれているので、Cの解決法が望ましいでしょう。

ありがとうございました。

Answer 1

すべてのサブセットに2つの要素がある場合、これはgraph isomorphismを表し、サブセットはグラフのエッジを表します。 これはさらに一般的です（したがっておそらくもっと難しい）ので、グラフ同型写像を解くために使用されるヒューリスティックを見て、ここで適用するかどうかを見てみましょう。

同形性を安価に除外できるグラフ同型写像のヒューリスティックがたくさんあります。特定のコレクションでは、各要素が属するサブセットの数を計算し、ソートすることができます。あなたの例では、両方のコレクションは[2,2,1,1,0,0,0,0]になります。 2つのコレクションのソートされたシーケンスが異なる場合、同形は存在しません。もちろん、平等は存在することを保証するものではありません。

非同形グラフをふるい分けるときには、もっとよく似た発見的方法があります（そして、ここに適用することもできます）。

また、8！ 40320だけなので、すべての順列をブルートフォースすることは全く不可能ではありません。