是否有一种快速算法可以将一个集合的所有分区生成为大小为 2 的子集（和一个大小为 1 的子集）？
Is there a fast algorithm for generating all partitions of a set into subsets of size 2 (and one subset of size 1)?
如标题所述，我正在尝试生成一组大小为 n 的所有分区，其中所有子集的大小为 2，如果 n 不均匀，则没有单例集。我非常轻微地修改了一些用于生成所有分区的 SO 代码来得到这个：
def partitionIntoPairs(collection):
if len(collection) == 1:
yield [ collection ]
return
first = collection[0]
for smaller in partition2(collection[1:]):
for n, subset in enumerate(smaller):
if len(subset):
yield smaller[:n] + [[ first ] + subset] + smaller[n+1:]
yield [ [ first ] ] + smaller
这可行，但遗憾的是太慢了。我的第二个想法是使用 itertools.combinations 为某个集合生成所有对，然后在不删除给定对的情况下为每个 det 递归调用该函数，但我猜这会更慢。此外，实现不正确，它只有 return 一种可能的分区，我不确定如何将其分配给 return 所有分区：
from itertools import combinations
def partitionIntoPairs2(collection):
if not collection:
return []
elif len(collection) == 1:
return [(next(iter(collection)))]
else:
pairs = set(combinations(collection, 2))
for pair in pairs:
collection.remove(pair[0])
collection.remove(pair[1])
return partition3(collection) + [pair]
我偶然发现了一些具有给定数量集合的分区算法，以及生成所有可能分区的算法的各种实现，但据我所知，这些都没有有效地解决我的问题。
因此，提出一个更具体的问题：如果第二种算法是可行的选择，那么正确的实现方式是什么？当然，有没有更快的方法来做到这一点？如果是，如何？
您的示例没有显示“所有子集”的含义。
如果您需要获取给定集中所有可能的值对，请尝试使用 set() 和 frozenset()
my_set = {1,2,3,}
res = set()
for value in my_set:
current_set = set()
current_set.add(value)
for value in my_set:
new_set = current_set.copy()
new_set.add(value)
res.add(frozenset(new_set))
if not len(my_set) % 2:
res = [list(new_set) for new_set in res if len(new_set) > 1]
else:
res = list(map(list, res))
print(res)
此递归生成器函数 yields 在分区长度与原始输入相同时进行分区，并且仅在它可以添加到正在进行的子分区或保留单个子分区时才进行递归调用（如果 len(data)%2 == 1）：
data = {1, 2, 3}
def partition(d, m, c = []):
if len(l:=[j for k in c for j in k]) == len(d):
yield c
for i in filter(lambda x:x not in l, d):
if not c or len(c[-1]) == m:
yield from partition(d, m, c=c+[[i]])
else:
if sum(len(i) == 1 for i in c) == 1 and len(data)%2:
yield from partition(d, m, c=c+[[i]])
yield from partition(d, m, c=[*c[:-1], c[-1]+[i]])
print(list(partition(list(data), 2)))
输出：
[[[1], [2, 3]], [[1, 2], [3]], [[1], [3, 2]], [[1, 3], [2]], [[2], [1, 3]], [[2, 1], [3]], [[2], [3, 1]], [[2, 3], [1]], [[3], [1, 2]], [[3, 1], [2]], [[3], [2, 1]], [[3, 2], [1]]]
当len(data)%2 == 0:
data = {1, 2, 3, 4}
print(list(partition(list(data), 2)))
输出：
[[[1, 2], [3, 4]], [[1, 2], [4, 3]], [[1, 3], [2, 4]], [[1, 3], [4, 2]], [[1, 4], [2, 3]], [[1, 4], [3, 2]], [[2, 1], [3, 4]], [[2, 1], [4, 3]], [[2, 3], [1, 4]], [[2, 3], [4, 1]], [[2, 4], [1, 3]], [[2, 4], [3, 1]], [[3, 1], [2, 4]], [[3, 1], [4, 2]], [[3, 2], [1, 4]], [[3, 2], [4, 1]], [[3, 4], [1, 2]], [[3, 4], [2, 1]], [[4, 1], [2, 3]], [[4, 1], [3, 2]], [[4, 2], [1, 3]], [[4, 2], [3, 1]], [[4, 3], [1, 2]], [[4, 3], [2, 1]]]
这可以用 itertools 完成，可能比递归算法更快，
就像另一个答案中的 partition ()。我在我的 timeit 序列中测量了 4.5s 的 t6 运行时间，如下所示，
相对于 mi_partition.
低于 0.2s 的时间
第一个想法是先列出集合的所有排列，然后拆分
每个都在子集中，使用 itertools 文档中的 grouper 算法
页。然后，如果适用，我们剔除最终奇数大小子集的填充物。
正如@Bing Wang 指出的那样，重复出现在这种类型的序列中。所以，
相反，我调用了 more_itertools.set_partitions 函数，它
减少重复。这也会生成长度更大的子集
大于 2，所以这些被过滤掉 itertools.filterfalse.
import itertools
import timeit
import more_itertools
t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)
def mi_partition(collection):
k = len(collection) // 2 + len(collection) % 2
s1 = more_itertools.set_partitions(collection, k)
if False:
p1, p2 = itertools.tee(s1)
print(len(list(p1)))
s1 = p2
return itertools.filterfalse(lambda x: any(len(y)>2 for y in x), s1)
print(list(mi_partition(t3)))
print(list(mi_partition(t4)))
输出：
[[[1], [2, 3]], [[1, 2], [3]], [[2], [1, 3]]]
[[[1, 2], [3, 4]], [[2, 3], [1, 4]], [[1, 3], [2, 4]]]
与 Partition 算法的小时间比较
@Bing Wang 的回答表明他们的解决方案更快：
def comp_timeit(collection, repeats=1_000):
s3 = f"l1 = list(mi_partition({collection}))"
s4 = f"l1 = list(Partition({collection}))"
t3 = timeit.timeit(s3, globals=globals(),number=repeats)
print(f"more_itertools, {repeats:_} runs: {t3:,.4f}")
t4 = timeit.timeit(s4, globals=globals(),number=repeats)
print(f"Partition, {repeats:_} runs: {t4:,.4f}")
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)
输出如下。请注意，对于 t3 到 t4，结果列表有
两种情况下的长度都是 3，而对于 t5，它的长度是 15。
似乎 Partitions 解决方案稍微快一些，可能
因为它不需要过滤任何解决方案。对于 t6，
set_partitions(t6, 3) 生成90个分区，只有15个
使其成为最终答案。
more_itertools, 1_000 runs: 0.0051
Partition, 1_000 runs: 0.0024
more_itertools, 1_000 runs: 0.0111
Partition, 1_000 runs: 0.0026
more_itertools, 1_000 runs: 0.1333
Partition, 1_000 runs: 0.0160```
分区应视为一个集合，两个仅顺序不同的分区应视为同一分区。所以数字集只有3个分区(1,2,3,4)。
分区数应该是N!/(N/2)!/2^(N/2)。使用斯特林公式，它大约是。 Sqrt(2)*(N/e)^(N/2) 其中 e=2.71828... 非常大。
我利用了@VirtualScooter 的代码并提供了 Partition 的递归版本，它比他的 itertools 版本运行得更快（注意这不是苹果对苹果的比较，因为我的 Partition 没有重复）。
import itertools
import timeit
t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)
def grouper(iterable, n, fillvalue=None):
"""Collect data into fixed-length chunks or blocks.
Code from Python itertools page
"""
# grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
args = [iter(iterable)] * n
return itertools.zip_longest(*args, fillvalue=fillvalue)
def partitionIntoPairs(collection):
perms = itertools.permutations(collection)
for p in perms:
group = list(grouper(p, 2))
if group[-1][-1] is None:
group[-1] = (group[-1][0],)
yield group
def Partition(Indexable):
if len(Indexable)<=2:
yield [Indexable]
elif len(Indexable)%2==1:
for i,x in enumerate(Indexable):
for s in Partition(Indexable[:i]+Indexable[i+1:]):
yield [[x]]+s
else:
for i,x in enumerate(Indexable):
if i==0:
x0=x
else:
for s in Partition(Indexable[1:i]+Indexable[i+1:]):
yield [[x0,x]]+s
def comp_timeit(collection, repeats=1_000):
s1 = f"l1 = list(Partition({collection}))"
s2 = f"l1 = list(partitionIntoPairs({collection}))"
t1 = timeit.timeit(s1, globals=globals(),number=repeats)
t2 = timeit.timeit(s2, globals=globals(),number=repeats)
print(f"partition, {repeats:_} runs: {t1:,.4f}")
print(f"itertools, {repeats:_} runs: {t2:,.4f}")
for p in Partition(t4):
print(p)
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)
如标题所述，我正在尝试生成一组大小为 n 的所有分区，其中所有子集的大小为 2，如果 n 不均匀，则没有单例集。我非常轻微地修改了一些用于生成所有分区的 SO 代码来得到这个：
def partitionIntoPairs(collection):
if len(collection) == 1:
yield [ collection ]
return
first = collection[0]
for smaller in partition2(collection[1:]):
for n, subset in enumerate(smaller):
if len(subset):
yield smaller[:n] + [[ first ] + subset] + smaller[n+1:]
yield [ [ first ] ] + smaller
这可行，但遗憾的是太慢了。我的第二个想法是使用 itertools.combinations 为某个集合生成所有对，然后在不删除给定对的情况下为每个 det 递归调用该函数，但我猜这会更慢。此外，实现不正确，它只有 return 一种可能的分区，我不确定如何将其分配给 return 所有分区：
from itertools import combinations
def partitionIntoPairs2(collection):
if not collection:
return []
elif len(collection) == 1:
return [(next(iter(collection)))]
else:
pairs = set(combinations(collection, 2))
for pair in pairs:
collection.remove(pair[0])
collection.remove(pair[1])
return partition3(collection) + [pair]
我偶然发现了一些具有给定数量集合的分区算法，以及生成所有可能分区的算法的各种实现，但据我所知，这些都没有有效地解决我的问题。
因此，提出一个更具体的问题：如果第二种算法是可行的选择，那么正确的实现方式是什么？当然，有没有更快的方法来做到这一点？如果是，如何？
您的示例没有显示“所有子集”的含义。 如果您需要获取给定集中所有可能的值对，请尝试使用 set() 和 frozenset()
my_set = {1,2,3,}
res = set()
for value in my_set:
current_set = set()
current_set.add(value)
for value in my_set:
new_set = current_set.copy()
new_set.add(value)
res.add(frozenset(new_set))
if not len(my_set) % 2:
res = [list(new_set) for new_set in res if len(new_set) > 1]
else:
res = list(map(list, res))
print(res)
此递归生成器函数 yields 在分区长度与原始输入相同时进行分区，并且仅在它可以添加到正在进行的子分区或保留单个子分区时才进行递归调用（如果 len(data)%2 == 1）：
data = {1, 2, 3}
def partition(d, m, c = []):
if len(l:=[j for k in c for j in k]) == len(d):
yield c
for i in filter(lambda x:x not in l, d):
if not c or len(c[-1]) == m:
yield from partition(d, m, c=c+[[i]])
else:
if sum(len(i) == 1 for i in c) == 1 and len(data)%2:
yield from partition(d, m, c=c+[[i]])
yield from partition(d, m, c=[*c[:-1], c[-1]+[i]])
print(list(partition(list(data), 2)))
输出：
[[[1], [2, 3]], [[1, 2], [3]], [[1], [3, 2]], [[1, 3], [2]], [[2], [1, 3]], [[2, 1], [3]], [[2], [3, 1]], [[2, 3], [1]], [[3], [1, 2]], [[3, 1], [2]], [[3], [2, 1]], [[3, 2], [1]]]
当len(data)%2 == 0:
data = {1, 2, 3, 4}
print(list(partition(list(data), 2)))
输出：
[[[1, 2], [3, 4]], [[1, 2], [4, 3]], [[1, 3], [2, 4]], [[1, 3], [4, 2]], [[1, 4], [2, 3]], [[1, 4], [3, 2]], [[2, 1], [3, 4]], [[2, 1], [4, 3]], [[2, 3], [1, 4]], [[2, 3], [4, 1]], [[2, 4], [1, 3]], [[2, 4], [3, 1]], [[3, 1], [2, 4]], [[3, 1], [4, 2]], [[3, 2], [1, 4]], [[3, 2], [4, 1]], [[3, 4], [1, 2]], [[3, 4], [2, 1]], [[4, 1], [2, 3]], [[4, 1], [3, 2]], [[4, 2], [1, 3]], [[4, 2], [3, 1]], [[4, 3], [1, 2]], [[4, 3], [2, 1]]]
这可以用 itertools 完成，可能比递归算法更快，
就像另一个答案中的 partition (mi_partition.
第一个想法是先列出集合的所有排列，然后拆分
每个都在子集中，使用 itertools 文档中的 grouper 算法
页。然后，如果适用，我们剔除最终奇数大小子集的填充物。
正如@Bing Wang 指出的那样，重复出现在这种类型的序列中。所以，
相反，我调用了 more_itertools.set_partitions 函数，它
减少重复。这也会生成长度更大的子集
大于 2，所以这些被过滤掉 itertools.filterfalse.
import itertools
import timeit
import more_itertools
t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)
def mi_partition(collection):
k = len(collection) // 2 + len(collection) % 2
s1 = more_itertools.set_partitions(collection, k)
if False:
p1, p2 = itertools.tee(s1)
print(len(list(p1)))
s1 = p2
return itertools.filterfalse(lambda x: any(len(y)>2 for y in x), s1)
print(list(mi_partition(t3)))
print(list(mi_partition(t4)))
输出：
[[[1], [2, 3]], [[1, 2], [3]], [[2], [1, 3]]]
[[[1, 2], [3, 4]], [[2, 3], [1, 4]], [[1, 3], [2, 4]]]
与 Partition 算法的小时间比较
@Bing Wang 的回答表明他们的解决方案更快：
def comp_timeit(collection, repeats=1_000):
s3 = f"l1 = list(mi_partition({collection}))"
s4 = f"l1 = list(Partition({collection}))"
t3 = timeit.timeit(s3, globals=globals(),number=repeats)
print(f"more_itertools, {repeats:_} runs: {t3:,.4f}")
t4 = timeit.timeit(s4, globals=globals(),number=repeats)
print(f"Partition, {repeats:_} runs: {t4:,.4f}")
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)
输出如下。请注意，对于 t3 到 t4，结果列表有
两种情况下的长度都是 3，而对于 t5，它的长度是 15。
似乎 Partitions 解决方案稍微快一些，可能
因为它不需要过滤任何解决方案。对于 t6，
set_partitions(t6, 3) 生成90个分区，只有15个
使其成为最终答案。
more_itertools, 1_000 runs: 0.0051
Partition, 1_000 runs: 0.0024
more_itertools, 1_000 runs: 0.0111
Partition, 1_000 runs: 0.0026
more_itertools, 1_000 runs: 0.1333
Partition, 1_000 runs: 0.0160```
分区应视为一个集合，两个仅顺序不同的分区应视为同一分区。所以数字集只有3个分区(1,2,3,4)。
分区数应该是N!/(N/2)!/2^(N/2)。使用斯特林公式，它大约是。 Sqrt(2)*(N/e)^(N/2) 其中 e=2.71828... 非常大。
我利用了@VirtualScooter 的代码并提供了 Partition 的递归版本，它比他的 itertools 版本运行得更快（注意这不是苹果对苹果的比较，因为我的 Partition 没有重复）。
import itertools
import timeit
t3 = (1, 2, 3)
t4 = (1, 2, 3, 4)
t6 = (1, 2, 3, 4, 5, 6)
def grouper(iterable, n, fillvalue=None):
"""Collect data into fixed-length chunks or blocks.
Code from Python itertools page
"""
# grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
args = [iter(iterable)] * n
return itertools.zip_longest(*args, fillvalue=fillvalue)
def partitionIntoPairs(collection):
perms = itertools.permutations(collection)
for p in perms:
group = list(grouper(p, 2))
if group[-1][-1] is None:
group[-1] = (group[-1][0],)
yield group
def Partition(Indexable):
if len(Indexable)<=2:
yield [Indexable]
elif len(Indexable)%2==1:
for i,x in enumerate(Indexable):
for s in Partition(Indexable[:i]+Indexable[i+1:]):
yield [[x]]+s
else:
for i,x in enumerate(Indexable):
if i==0:
x0=x
else:
for s in Partition(Indexable[1:i]+Indexable[i+1:]):
yield [[x0,x]]+s
def comp_timeit(collection, repeats=1_000):
s1 = f"l1 = list(Partition({collection}))"
s2 = f"l1 = list(partitionIntoPairs({collection}))"
t1 = timeit.timeit(s1, globals=globals(),number=repeats)
t2 = timeit.timeit(s2, globals=globals(),number=repeats)
print(f"partition, {repeats:_} runs: {t1:,.4f}")
print(f"itertools, {repeats:_} runs: {t2:,.4f}")
for p in Partition(t4):
print(p)
comp_timeit(t3)
comp_timeit(t4)
comp_timeit(t6)