python - 生成一组整数的不相交子集的无序对

Question

我正在尝试生成一组整数 S 的不相交子集的无序对。如 [1] 所示，当 S 由 n 个整数组成时，我们生成大约 3 ⁿ /2 对。现在，我知道如何生成 S 的所有 2 ⁿ个子集（即 S 的幂集），并且对于每个子集（由 k 个整数组成），我可以因此生成 kC2（k 选择 2）个可能的对。但这是低效的，因为配对最终会生成不止一次。

因此，我想知道是否有一些有效的（递归）方法可以从 S 生成这些子集对？到目前为止，我找不到任何现有的实现，并且我自己使用 Python 的 itertools 的尝试也没有成功。

[1] S的不相交子集的无序对的总数（MathOverflow）

标签： pythonrecursionsubsetcombinationsitertools