サイズkの最も一般的なサブセット

Question

整数範囲R={1,2,...,N}のサブセットS1,...,Snと整数kのリストがあるとします。サブセットを見つける効率的な方法は、サイズkのRのCがあり、CがSiの最大数のサブセットですか？

例として、そして、私は（これは関係ありません）C={1,2}かC={1,3}のいずれかを返すようにしたいR={1,2,3,4}とk=2

S1={1,2,3} 
S2={1,2,3} 
S3={1,2,4} 
S4={1,3,4} 

をしましょう。

Answer 1

あなたの問題はNP-Hardだと思います。左側のノードがあなたのセットであり、右側のノードが整数{1, ..., N}である二部グラフを考えてください。セットに整数が含まれている場合は、2つのノード間にエッジがあります。次に、Siの最大数のサブセットであるサイズkの共通サブセットを見つけることは、最大端数がi*kである完全二部構成サブグラフK(i, k)を見つけることと同じです。これを多項式時間で行うことができれば、kの各固定値を試して、多項式時間で最大の辺の数がi*jである完全な2部グラフサブグラフK(i, j)を見つけることができます。しかし、NP-Complete（Complete bipartite graph）のこの問題。

したがって、P = NPでなければ、問題には多項式時間アルゴリズムがありません。

Answer 2

私があなたの質問を理解しているとすれば、これはかなり小さいセットでは簡単だと思います。

私はMathematicaのコードを使って説明しますが、概念は普遍的です。

Iは集合{1 .. 8}から、長さ4の10ランダムサブセットを生成する：

ss = Subsets[Range@8, {4}] ~RandomSample~ 10 

{{1, 3, 4, 6}, {2, 6, 7, 8}, {3, 5, 6, 7}, {2, 4, 6, 7}, {1, 4, 5, 8}, 
{2, 4, 6, 8}, {1, 2, 3, 8}, {1, 6, 7, 8}, {1, 2, 4, 7}, {1, 2, 5, 7}} 

Iは、これらの各番号の存在のバイナリ列に変換します各サブセット内で：

a = Normal@SparseArray[Join @@ MapIndexed[Tuples[{##}] &, ss] -> 1]; 

Grid[a] 

これは、10個のサブセットに対して10個の列、要素{1. ... 8}用に8個の行です。

ここで全ての可能なターゲットのサブセット（サイズ3）を生成する：

keys = Subsets[Union @@ ss, {3}]; 

は、次いで、（すべての列が1に等しいときに限り1を返す）「キー」を取り、アレイからそれらの行を抽出し、BITAND動作を行います1の数を数えます。例えば、キー{1, 6, 8}のために、私たちは持っている：BITAND後

a[[{1, 6, 8}]] 

：

は、各キーのためにこれを行います

counts = Tr[BitAnd @@ a[[#]]] & /@ keys; 

が続いて位置を見つけます最大要素の数（s）そのリストF、及びkeysの対応する部分を抽出する：十分なメモリを有する

keys ~Extract~ Position[counts, Max@counts] 

{{1, 2, 7}, {2, 4, 6}, {2, 4, 7}, {2, 6, 7}, {2, 6, 8}, {6, 7, 8}} 

このプロセスは、より大きなセットのために迅速に働きます。 {1 ... 30}から長7の50,000ランダムに選択されたサブセットで始まる：長4の

ss = Subsets[Range@30, {7}] ~RandomSample~ 50000; 

最大サブサブセットは約9秒で計算される：

AbsoluteTiming[ 
    a = Normal@SparseArray[Join @@ MapIndexed[Tuples[{##}] &, ss] -> 1]; 
    keys = Subsets[Union @@ ss, {4}]; 
    counts = Tr[BitAnd @@ a[[#]]] & /@ keys; 
    keys~Extract~Position[counts, Max@counts] 
] 

{8.8205045, {{2, 3, 4, 20}, 
       {7, 10, 15, 18}, 
       {7, 13, 16, 26}, 
       {11, 21, 26, 28}}} 

これを追加する必要がありますMathematicaは高水準言語であり、これらの操作は汎用オブジェクトにありますこれが本当にバイナリレベルで行われるならば、これははるかに速く、よりメモリ効率が良いはずです。ここで私は、私は問題を誤解しないことを望む

Answer 3

... SWI-Prologの中で溶液

:- module(subsets, [solve/0]). 
:- [library(pairs), 
    library(aggregate)]. 

solve :- 
    problem(R, K, Subsets), 
    once(subset_of_maximal_number(R, K, Subsets, Subset)), 
    writeln(Subset). 

problem(4, 2, 
[[1,2,3], [1,2,3], [1,2,4], [1,3,4]]). 

problem(8, 3, 
[[1, 3, 4, 6], [2, 6, 7, 8], [3, 5, 6, 7], [2, 4, 6, 7], [1, 4, 5, 8], 
[2, 4, 6, 8], [1, 2, 3, 8], [1, 6, 7, 8], [1, 2, 4, 7], [1, 2, 5, 7]]). 

subset_of_maximal_number(R, K, Subsets, Subset) :- 
    flatten(Subsets, Numbers), 
    findall(Num-Count, 
     ( between(1, R, Num), 
      aggregate_all(count, member(Num, Numbers), Count) 
     ), NumToCount), 
    transpose_pairs(NumToCount, CountToNumSortedR), 
    reverse(CountToNumSortedR, CountToNumSorted), 
    length(Subset, K), % list of free vars 
    prefix(SolutionsK, CountToNumSorted), 
    pairs_values(SolutionsK, Subset). 

テスト出力：

?- solve. 
[1,3] 
true ; 
[7,6,2] 
true. 

編集：は、私が思う上記の溶液は、戻り値は入力のサブセットではないという意味で間違っています。この問題のないここの（コメント付きの）ソリューション：

:- module(subsets, [solve/0]). 
:- [library(pairs), 
    library(aggregate), 
    library(ordsets)]. 

solve :- 
    problem(R, K, Subsets), 
    once(subset_of_maximal_number(R, K, Subsets, Subset)), 
    writeln(Subset). 

problem(4, 2, 
[[1,2,3], [1,2,3], [1,2,4], [1,3,4]]). 

problem(8, 3, 
[[1, 3, 4, 6], [2, 6, 7, 8], [3, 5, 6, 7], [2, 4, 6, 7], [1, 4, 5, 8], 
[2, 4, 6, 8], [1, 2, 3, 8], [1, 6, 7, 8], [1, 2, 4, 7], [1, 2, 5, 7]]). 

subset_of_maximal_number(R, K, Subsets, Subset) :- 
    flatten(Subsets, Numbers), 
    findall(Num-Count, 
     ( between(1, R, Num), 
      aggregate_all(count, member(Num, Numbers), Count) 
     ), NumToCount), 

    % actually sort by ascending # of occurrences 
    transpose_pairs(NumToCount, CountToNumSorted), 
    pairs_values(CountToNumSorted, PreferredRev), 

    % we need higher values first 
    reverse(PreferredRev, Preferred), 

    % empty slots to fill, preferred first 
    length(SubsetP, K), 
    select_k(Preferred, SubsetP), 

    % verify our selection it's an actual subset of any of subsets 
    sort(SubsetP, Subset), 
    once((member(S, Subsets), ord_subtract(Subset, S, []))). 

select_k(_Subset, []). 
select_k(Subset, [E|R]) :- 
    select(E, Subset, WithoutE), 
    select_k(WithoutE, R). 

テスト：これは頻繁サブセットマイニング/バスケットマイニングによく似ています

?- solve. 
[1,3] 
true ; 
[2,6,7] 
true.