将列表拆分为最少集合的最快方法，枚举所有可能的解决方案
假设我有一个带有重复项的数字列表。
import random
lst = [0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 9]
random.shuffle(lst)
我想将列表拆分为最少数量的子“集”，其中包含所有唯一数字，而不丢弃任何数字。我设法编写了以下代码，但我觉得这是硬编码的，因此应该有更快更通用的解决方案。
from collections import Counter
counter = Counter(lst)
maxcount = counter.most_common(1)[0][1]
res = []
while maxcount > 0:
res.append(set(x for x in lst if counter[x] >= maxcount))
maxcount -= 1
assert len([x for st in res for x in st]) == len(lst)
print(res)
输出：
[{4}, {8, 2, 4}, {0, 2, 3, 4, 7, 8}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}]
显然，这只是解决方案之一。另一种解决方案可能是
[{4, 9}, {8, 2, 4}, {0, 2, 3, 4, 7, 8}, {0, 1, 2, 3, 4, 5, 6, 7, 8}]
我想用最少的子“集”（在这种情况下为 4）找到所有可能的解决方案。需要注意的是相同的数字是无法区分的，例如[{1}, {1, 2}]是相同的溶液[{1, 2}, {1}]用于名单[1, 2, 1]。
有什么建议？
回答
这种方式花费的时间与列表元素的数量呈线性关系，并且无论输入列表的顺序如何，其输出都是相同的（相同的集合，相同的顺序）。它基本上是您代码的一个更“热切”的变体：
def split(xs):
from collections import defaultdict
x2count = defaultdict(int)
result = []
for x in xs:
x2count[x] += 1
count = x2count[x]
if count > len(result):
result.append(set())
result[count - 1].add(x)
return result
然后，例如，
xs = [0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 9]
import random
random.shuffle(xs)
print(split(xs))
显示
[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 2, 3, 4, 7, 8}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 2, 3, 4, 7, 8}, {8, 2, 4}, {4}]
找到所有答案肯定会很烦人 😉 但足够直截了当。一旦你知道结果中有 4 个集合，那么你就有了一个毛茸茸的笛卡尔积来计算。你知道，例如，7 出现两次，所以有comb(4, 2) == 6办法选择 7 进入的两个结果集。对于这些方式中的每一种，你知道，例如，8 出现 3 次，所以有comb(4, 3) == 4办法选择三个结果设置 8 进入。现在我们最多有 6 * 4 = 24 个部分结果。对所有其他原始整数重复类似的操作。itertools.combinations()可以用来做选择。
不清楚：考虑输入[1, 1, 2]。这里的输出是[{1, 2}, {1}]。您是否认为这与[{1}, {1, 2}]? 也就是说，您认为输出是一系列集合（在这种情况下它们是不同的），还是作为一组集合（在这种情况下它们是相同的）？一个简单的笛卡尔积采用“它是一个序列”的观点。
找到所有的人
这是一个方法。如图所示，它计算在所需输出集数量上分布每个元素的所有方式的笛卡尔积。但它不是itertools.product()用于此，而是递归执行，一次一个元素。这允许它检查到目前为止的同构的部分结果，并拒绝将任何同构的部分解决方案扩展到它已经扩展的部分解决方案。
为此，它将部分解决方案视为一组集合。出于技术原因，Python 需要将 afrozenset用于集合，该集合将依次用作集合元素。
注意：这个生成器每次都会产生相同的 result对象。那是为了效率。如果你不喜欢那样，你可以，例如，更换
和
yield result
反而。
编辑：请注意，我替换了该行
sig = frozenset(map(frozenset, result))
sig = frozenset(map(frozenset, result))
和
sig = frozenset(Counter(map(frozenset, result)).items())
那是因为您实际上并没有将结果视为一组集合，而是将其视为一组多组（一个给定的集合可以在结果中出现多次，而且出现的次数很重要）。在比这里给出的更高级的测试用例中，这可以产生真正的不同。
ACounter是 Python 与内置多集类型最接近的东西，但没有Counter类似于frozensets 的“冻结”工作方式。因此，我们将Counter转化为 2 元组序列，并将这些元组放入frozenset。通过使用(set, count)对，这使我们能够解释一个集合在结果中出现的次数是重要的。
yield result[:]
例子：
对于您的原始示例，它找到了 36992 种对输入进行分区的独特方法。