algorithm - 如何找到多重集的所有分区(允许重复的集合)

Question

给定一个可能包含重复项的数字集合，找到它的所有分区。 (所有可能的划分集合的方式。)

例如，多重集 {1, 1, 2} 有 4 个分区:

分区 1 = { {1}, {1}, {2} } 分区 2 = { {1}, {1, 2} } 分区 3 = { {1, 1}, {2} } 分区 4 = { {1, 1, 2} }

这里有一个类似的问题How to find all partitions of a set但在那个问题中，所有数字都是不同的。

集合分区的定义:https://en.wikipedia.org/wiki/Partition_of_a_set

多重集的定义: https://en.wikipedia.org/wiki/Multiset

将不胜感激用任何常见编程语言编写的带有一些解释的解决方案。

---

更新:

似乎很多人都搞不清楚这个问题在问什么。它不是要求给定集合的所有可能子集。相反，它要求您找出划分给定数字集合的所有不同方法。

Answer 1

嘿，我有一个 python 解决方案:

from sympy.utilities.iterables import multiset_partitions

for pi in multiset_partitions([1,1,3]):
    print(pi)

看代码，可以在Knuth's AOCP中找到算法

算法 M，第 39-40 页。

AOCP 是 also described here

请参阅第 3b 卷，算法 M，第 39-40 页。