2

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

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

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

0b11000000, 0b01100000, 0b00110000

の複製です

0b00110000, 0b00011000, 0b00100100

前者は順列を適用することで後者から取得できるためです

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

結果を並べ替えます。

パフォーマンスを考慮して、配列には約2000行が含まれ、各行は最大20個の要素で構成されます。各行はすでに順序付けられており、これが役立つ場合は、行も辞書式順序で並べられています。アルゴリズムの残りの部分はCで記述されているため、Cソリューションが推奨されます。

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

4

1 に答える 1

0

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

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

同形でないグラフをふるい分けるのにさらに優れた同様のヒューリスティックが他にもたくさんあります (ここで適用される可能性があります)。

また、8！は 40320 しかないため、すべての順列をブルート フォーシングすることはまったく不可能というわけではありません。

于 2009-07-03T09:53:53.880 に答える