生成 k 个最子集唯一元素对

Question

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

f(a,b)

=

f(b,a)

因此，我想生成最大大小为 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,8}

的交集是

{2,6}

。

Answer 1

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

Answer 2

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

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

如果我们固定子集的大小（k=3 而不是 k<=3) you want, this is easy to do in an non-efficient manner:

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

一些问题由此而来

1. 有没有更有效的方法来做到这一点
2. 固定 k 会改变这个解决方案吗？始终采用最大尺寸的子集是否是最佳方案？ 是否有一个最佳集合可以让我们选择尺寸 t
3. 对于<=k and have all the subsets be of that size
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

你可以这样做：

Answer 3

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