生成k個最獨特的子集對元素

我寫一個應用程序Cuda的應該在我的集合S的兩個元素，但對順序犯規任何區別計算的功能，所以：f(a,b) = f(b,a)生成k個最獨特的子集對元素

出於這個原因，我想要生成最大大小爲K的S的所有子集，而不需要在集合之間複製元素對。

換句話說，給定任何兩個子集，我不希望它們的交集大於一個元素。（這樣我可以避免計算這兩個元件的多次的功能）

實施例：

鑑於S={1,2,3,4,5,6,7,8,9}和K=3，輸出應該是這樣的：

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

但輸出應不是這樣的：

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

因爲{2,4,6}和的交集是{2,6}。

來源

2012-04-28 user1363214

什麼是你的問題？ – 2012-04-28 18:22:40

你能花些時間寫下你的問題嗎？它應該包含一個[簡短，獨立，正確的例子]（http://sscce.org/）;清楚描述問題所在，並描述[您嘗試過的]（http://mattgemmell.com/2008/12/08/what-have-you-tried/）。 – Ben 2012-04-28 18:23:45

我想你可能會不小心遺漏了你的問題的某些部分。 – 2012-04-28 18:26:35

我要張貼，希望非的答案可以幫助我們釘了一個問題：我在下面回答的問題是

給定一組S，產生最大基數集中所有的 S的子集，使得每個子集小於大小K和兩個子集合不包含基數> 1

的交點如果我們固定子集的大小（K = 3，而大於k < = 3）你想，這很容易以非效率的方式完成：

生成大小爲k的所有子集選自S
請取出的東西，直到沒有交集存在

有些問題來自這個

有沒有更有效的方式做到這
是否不是固定k改變這個解決方案，是最佳的總是取最大的子集大小
是否存在最佳的設定，使得我們可以選擇一個大小T < = k和擁有所有的子集是大小

的對於2）我想答案是否定的：

觀察：對於小的N，簡單地生成對比生成大小爲K的子集要好。生成大小> 2的子集只消除一對，生成k的子集消除k選擇2對。選擇大小K是隻有更好，如果

n/(k choose 2) = k/(k!/(k-2)!2!) = 2n/(k*(k-1)) > (n*n-1)/2 = (n choose 2) 
1/(k*(k-1)) > (n-1)/4n

僅限足夠大的N，這是真的：

1/(k*(k-1)) > 1/4 
    (k*(k-1)) > 4, k>=3

對於3）我想答案是肯定的

數子集的最大值爲C(n,k)/C(k,2)，我們可以使用公式計算這個值來找到最優的k。如果有仍然對，我們可以簡單地添加那些到列表中，就好像K = 2

來源

2012-04-28 19:18:33 dfb

@ user1363214在這裏重新發布我的最後一條評論：我認爲你的謂詞中有一個非交換性問題;爲了從您的原始問題中得到您的榜樣，您希望應用什麼規則來區分{2,4,6}和{2,6,8}：您期望{2,4,6}，{2 ，8}，但你爲什麼不期待{2,4}，{2,6,8}？ ... – Boud 2012-04-28 19:19:21

@Boud - 這是針對OP，對吧？ – dfb 2012-04-28 19:19:50

你是對的，只是加了'@'標記 – Boud 2012-04-28 19:21:36

>>> from itertools import combinations, chain 
>>> s = {1,2,3,4,5,6,7,8,9} 
>>> k = 3 
>>> seen = set() 
>>> subset_sizes = reversed(range(2,k+1)) # [3,2] for this example. Reversed since you favor the sets with larger values of K 
>>> for item in chain.from_iterable(combinations(s,i) for i in subset_sizes): 
     pairs = set(combinations(item,2)) 
     if not pairs.intersection(seen): 
      seen.update(pairs) 
      print item 


(1, 2, 3) 
(1, 4, 5) 
(1, 6, 7) 
(1, 8, 9) 
(2, 4, 6) 
(2, 5, 7) 
(3, 4, 7) 
(3, 5, 6) 
(2, 8) 
(2, 9) 
(3, 8) 
(3, 9) 
(4, 8) 
(4, 9) 
(5, 8) 
(5, 9) 
(6, 8) 
(6, 9) 
(7, 8) 
(7, 9)

來源

2012-04-28 21:11:22 jamylak

，你可以這樣做：

P := {1, 2, 3, 4, 5, 6}; setpartition(P, 3); 
    {{{1, 2, 3}, {4, 5, 6}}, {{1, 2, 4}, {3, 5, 6}}, 

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

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

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

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

來源

2012-05-16 08:00:09 user1349573

生成k個最獨特的子集對元素

回答

相關問題