假设我有一个带有复制人的数字列表。
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}]
找到所有答案注定很烦人;-)但足够直截了当。一旦你知道结果中有 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 需要对一个集合使用frozenset，该集合将依次用作集合元素。
注意：此生成器每次都会生成相同的result对象。这是为了效率。如果您不喜欢这样，您可以，例如，替换
yield result
跟
yield result[:]
相反。
编辑：请注意我替换了该行
sig = frozenset(map(frozenset, result))
跟
sig = frozenset(Counter(map(frozenset, result)).items())
这是因为您实际上不是将结果视为一组集合，而是作为多组集合(给定集合可以在结果中出现多次，并且它出现的次数很重要)。在比这里给出的更花哨的测试用例中，这可以产生真正的不同。
Counter是Python最接近内置多集类型的东西，但是没有类似于冻结集的"冻结"Counter工作。因此，我们将Counter转换为 2 元组序列，并将这些元组放入冻结集中。通过使用(set, count)对，这使我们能够解释集合在结果中出现的次数是显着的。
def allsplit(xs):
from collections import Counter
from itertools import combinations
c = Counter(xs)
n = max(c.values())
result = [set() for i in range(n)]
pairs = list(c.items())
pin = len(pairs)
def inner(pi):
if pi >= pin:
yield result
return
elt, count = pairs[pi]
seen = set()
for ixs in combinations(range(n), count):
for i in ixs:
result[i].add(elt)
sig = frozenset(Counter(map(frozenset, result)).items())
if sig not in seen:
yield from inner(pi + 1)
seen.add(sig)
for i in ixs:
result[i].remove(elt)
return inner(0)
例：
>>> for x in allsplit([1, 1, 2, 3, 8, 4, 4]):
... print(x)
[{1, 2, 3, 4, 8}, {1, 4}]
[{1, 2, 3, 4}, {8, 1, 4}]
[{1, 2, 4, 8}, {1, 3, 4}]
[{1, 2, 4}, {1, 3, 4, 8}]
对于原始示例，它找到了 36992 种对输入进行分区的独特方法。
我建议使用预填充列表，然后将每个值存储在单独的存储桶中
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
我的简单解决方案，从大到小返回集合：
# Problem definition
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)
# Divide in sets, biggest first
l = lst.copy()
sets = []
while l:
sets.append(set(l))
for item in sets[-1]:
l.remove(item)
现在困难的部分，组合。我建议从类似和扩展的东西开始，接下来只是一个概念证明，除了琐碎的"移动整个差异集"之外，避免重复。真正的实现将涵盖集合->集合传输的所有组合(只需添加另一个 itertools.combination 级别)，但我不知道如何以一种巧妙的方式并行处理将元素从不同的集合移动到不同的集合。
import itertools
more_sets = [sets]
diff_0_1 = sets[0] - sets[1]
for comb_size in range(1, len(diff_0_1)):
for comb in itertools.combinations(diff_0_1, comb_size):
s0 = sets[0] - set(comb)
s1 = sets[1] | set(comb)
more_sets.append([s0, s1] + sets[2:])
for some_sets in more_sets:
print(some_sets)
上面的代码返回以下内容：
~ python3.8 tmp.py
[{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 2, 3, 4, 7, 8}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 5, 6, 7, 8, 9}, {0, 1, 2, 3, 4, 7, 8}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 6, 7, 8, 9}, {0, 2, 3, 4, 5, 7, 8}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 5, 7, 8, 9}, {0, 2, 3, 4, 6, 7, 8}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 5, 6, 7, 8}, {0, 2, 3, 4, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 6, 7, 8, 9}, {0, 1, 2, 3, 4, 5, 7, 8}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 5, 7, 8, 9}, {0, 1, 2, 3, 4, 6, 7, 8}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 5, 6, 7, 8}, {0, 1, 2, 3, 4, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 7, 8, 9}, {0, 2, 3, 4, 5, 6, 7, 8}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 6, 7, 8}, {0, 2, 3, 4, 5, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 5, 7, 8}, {0, 2, 3, 4, 6, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 7, 8, 9}, {0, 1, 2, 3, 4, 5, 6, 7, 8}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 6, 7, 8}, {0, 1, 2, 3, 4, 5, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 2, 3, 4, 5, 7, 8}, {0, 1, 2, 3, 4, 6, 7, 8, 9}, {8, 2, 4}, {4}]
[{0, 1, 2, 3, 4, 7, 8}, {0, 2, 3, 4, 5, 6, 7, 8, 9}, {8, 2, 4}, {4}]