4

我正在编写一个 Cuda 应用程序，它应该在我的集合 S 的两个元素上计算一个函数。但是这对的顺序没有任何区别，所以：f(a,b)=f(b,a)

出于这个原因，我想生成最大大小为 K 的 S 的所有子集，而不会在集合之间复制元素对。

换句话说，给定任何两个子集，我不希望它们的交集大于一个元素。（这样我可以避免多次计算这两个元素的函数）

例子：

给定S={1,2,3,4,5,6,7,8,9}and 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,8}是{2,6}。

4

3 回答 3

0

我将发布一个非答案，希望它可以帮助我们确定问题：我在下面回答的问题是

给定一个集合 S，生成 S 的所有子集的最大基数集，使得每个子集都小于大小 K，并且没有两个子集包含基数 > 1 的交集

如果我们固定您想要的子集的大小（k=3 而不是 k<=3），这很容易以一种非有效的方式进行：

  1. 从 S 生成所有大小为 k 的子集
  2. 继续移除东西，直到没有交叉点存在

一些问题由此而来

  1. 有没有更有效的方法来做到这一点
  2. 不固定 k会改变这个解决方案，总是采用最大尺寸的子集是最优的吗
  3. 是否存在一个最优集合，以便我们可以选择一个大小 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-28T19:18:33.303 回答
0 
>>> 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-28T21:11:22.517 回答
0

你可以这样做 ：

    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-16T08:00:09.710 回答