此问题已在此处有答案:
How to find all partitions of a set(8个回答)
5天前关闭。
现在我正在研究n辆汽车的通信,我遇到的问题可以简化为:
n个数字,我想得到所有的子集,满足条件的是它们被划分(像下面的例子),所有这些n个数字都被全部使用并且只使用一次。
例如,如果n = 3,则可以将它们分为:
[[1, 2, 3]]
[[1, 2], [3]]
[[1, 3], [2]]
[[2, 3], [1]]
[[1], [2], [3]]
我试过用c++用next_permutation函数来解决(因为它没有任何组合问题的函数),但失败了,因为它输出了太多重复的答案(比如[1 2][3]
和[2 1][3]
,实际上是一样的,但我不知道怎么识别)
我认为我的想法是错误的使用这个功能。
1条答案
按热度按时间8i9zcol21#
您要查找的是partitions,而不是组合或排列。
您可以通过注意到如果 P,来找到具有 n 个成员的集合 S 的分区。(n-1)是 S-a 的划分,其中 a 是任意成员,则可以构造 P(n)作为包含插入到 P 的每个成员中的 a 的集合也就是说,如果 q 是 P 中的某个分区,(n-1),为了构建 P(n)中的分区,a 可以是附加到 q 的单例集合,或者 a 可以附加到已经在 q 中的集合之一。
代码如下: