生成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 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

@ 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)

答

，你可以这样做：

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}}}

生成k个最独特的子集对元素

相关推荐