python - 将列表划分为最少集合的最快方法，枚举所有可能的解决方案

Question

假设我有一个带有重复项的数字列表。

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] 列表。
有什么建议么？

Answer 1

我建议使用预填充列表然后将每个值存储在单独的存储桶中

import random
from collections import Counter

lst = [0, 0, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 9]
random.shuffle(lst)

c = Counter(lst)
maxcount = c.most_common(1)[0][1]
result = [set() for _ in range(maxcount)]
for k, v in c.items():
    for i in range(v):
        result[i].add(k)

print(result)

也可以用 defaultdict 来实现

c = Counter(lst)
result = defaultdict(set)
for k, v in c.items():
    for i in range(v):
        result[i].add(k)
result = list(result.values())
print(result)

性能注意事项

from timeit import timeit
import numpy as np
lst = list(np.random.randint(0, 100, 10000))
nb = 1000
print(timeit(lambda: prefilled_list(lst), number=nb))   # 2.144
print(timeit(lambda: default_dict_set(lst), number=nb)) # 1.903
print(timeit(lambda: op_while_loop(lst), number=nb))    # 318.2