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