我想在所有可能的组合中将列表拆分为n组(允许变量组长度).
说,我有以下列表:
lst=[1,2,3,4]
如果我指定n = 2,则可以将列表分成1个元素-3元素或2个元素-2元素的组.在这两种分割列表的方式中,每个列表中都有各种元素的唯一组合.
当n = 2时,这些将是:
(1),(2,3,4)
(2),(1,3,4)
(3),(1,2,4)
(4),(1,2,3)
(1,2),(3,4)
(1,3),(2,4)
(1,4),(2,3)
当n = 1时,这些将是:
(1,2,3,4)
n = 3时,这些将是:
(1),(2),(3,4)
(1),(3),(2,4)
(1),(4),(2,3)
(2),(3),(1,4)
(2),(4),(1,3)
(3),(4),(1,2)
我对长度为0的组不感兴趣,并且组内的顺序无关紧要.
我发现了两个类似的问题,但他们并没有完全回答我的问题.
这个问题将列表分成所有组合,其中每个组的长度为n(我发现@tokland的答案)特别有用).但是,我并不是要寻找所有组长度相同的组.
然后,此问题的第一步获得拆分位置的独特组合,以将列表拆分为n个组.但是,此处保留了列表顺序,并且未确定这些组中元素的唯一组合.
我正在寻找这两个问题的组合 - 列表在组长度的所有可能组合中分成n组,以及组内元素的组合.
我们可以使用此答案中的基本递归算法并对其进行修改以生成特定长度的分区,而无需生成和过滤掉不需要的分区.
def sorted_k_partitions(seq, k):
"""Returns a list of all unique k-partitions of `seq`.
Each partition is a list of parts, and each part is a tuple.
The parts in each individual partition will be sorted in shortlex
order (i.e., by length first, then lexicographically).
The overall list of partitions will then be sorted by the length
of their first part, the length of their second part, ...,
the length of their last part, and then lexicographically.
"""
n = len(seq)
groups = [] # a list of lists, currently empty
def generate_partitions(i):
if i >= n:
yield list(map(tuple, groups))
else:
if n - i > k - len(groups):
for group in groups:
group.append(seq[i])
yield from generate_partitions(i + 1)
group.pop()
if len(groups) < k:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
result = generate_partitions(0)
# Sort the parts in each partition in shortlex order
result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
# Sort partitions by the length of each part, then lexicographically.
result = sorted(result, key = lambda ps: (*map(len, ps), ps))
return result
这里有很多事情,所以让我解释一下.
首先,我们从相同的上述递归算法的程序性,自下而上(teminology？)实现开始:
def partitions(seq):
"""-> a list of all unique partitions of `seq` in no particular order.
Each partition is a list of parts, and each part is a tuple.
"""
n = len(seq)
groups = [] # a list of lists, currently empty
def generate_partitions(i):
if i >= n:
yield list(map(tuple, groups))
else:
for group in groups
group.append(seq[i])
yield from generate_partitions(i + 1)
group.pop()
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
if n > 0:
return list(generate_partitions(0))
else:
return [[()]]
主要算法是嵌套generate_partitions函数.基本上,它遍历序列,并且对于每个项目,它:1)将项目放入工作集中的每个当前组(也称为部分)并递归; 2)将项目放在自己的新组中.
当我们到达序列(i == n)的末尾时,我们得到了我们一直在构建的工作集的(深层)副本.
现在,为了获得特定长度的分区,我们可以简单地过滤或分组我们正在寻找的分区的结果并完成它,但是如果我们只是想要这个方法执行许多不必要的工作(即递归调用)一些长度的分区k.
请注意,在上面的函数中,只要以下情况,分区的长度(即组的数量)就会增加:
# this adds a new group (or part) to the partition
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
......被执行了.因此,我们通过简单地在该块上放置一个保护来限制分区的大小,如下所示:
def partitions(seq, k):
...
def generate_partitions(i):
...
# only add a new group if the total number would not exceed k
if len(groups) < k:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
将新参数和该行添加到该partitions函数现在将使其仅生成长度最多的 分区k.这几乎就是我们想要的.问题是for循环有时仍会生成长度小于的 分区k.
为了修剪那些递归分支,我们只需要for在我们可以确保在序列中有足够的剩余元素来将工作集扩展为总计k组时执行循环.剩余元素的数量 - 或尚未放入组中的元素 - 是n - i(或len(seq) - i).并且k - len(groups)是我们需要添加以生成有效k分区的新组的数量.如果n - i <= k - len(groups),那么我们不能通过添加一个当前组来浪费项目 - 我们必须创建一个新组.
所以我们只是添加另一个后卫,这次是另一个递归分支:
def generate_partitions(i):
...
# only add to current groups if the number of remaining items
# exceeds the number of required new groups.
if n - i > k - len(groups):
for group in groups:
group.append(seq[i])
yield from generate_partitions(i + 1)
group.pop()
# only add a new group if the total number would not exceed k
if len(groups) < k:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
有了它,你有一个工作的k分区生成器.您甚至可以进一步折叠一些递归调用(例如,如果剩下3个项目,我们还需要3个组,那么您已经知道必须将每个项目拆分成他们自己的组),但我想显示作为生成所有分区的基本算法的略微修改.
剩下要做的就是对结果进行排序.不幸的是,我没有弄清楚如何以所需的顺序直接生成分区(一个聪明的狗的练习),而是欺骗了,只是对后代进行了分类.
def sorted_k_partitions(seq, k):
...
result = generate_partitions(0)
# Sort the parts in each partition in shortlex order
result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
# Sort partitions by the length of each part, then lexicographically.
result = sorted(result, key = lambda ps: (*map(len, ps), ps))
return result
除了关键功能外,有些不言自明.第一个:
key = lambda p: (len(p), p)
表示按长度排序序列,然后按序列本身排序(在Python中,默认情况下按字典顺序排序).该p代表"组成部分".这用于对分区中的部件/组进行排序.这个键意味着,例如,(4,)在前面(1, 2, 3),因此[(1, 2, 3), (4,)]被排序为[(4,), (1, 2, 3)].
key = lambda ps: (*map(len, ps), ps)
# or for Python versions <3.5: lambda ps: tuple(map(len, ps)) + (ps,)
在ps这里代表"零件",复数.这个说按顺序排列每个元素的长度(必须是序列本身),然后(按字典顺序)由序列本身.这用于相对于彼此对分区进行排序,以便例如[(4,), (1, 2, 3)]在前面[(1, 2), (3, 4)].
下列:
seq = [1, 2, 3, 4]
for k in 1, 2, 3, 4:
for groups in sorted_k_partitions(seq, k):
print(k, groups)
生产:
1 [(1, 2, 3, 4)]
2 [(1,), (2, 3, 4)]
2 [(2,), (1, 3, 4)]
2 [(3,), (1, 2, 4)]
2 [(4,), (1, 2, 3)]
2 [(1, 2), (3, 4)]
2 [(1, 3), (2, 4)]
2 [(1, 4), (2, 3)]
3 [(1,), (2,), (3, 4)]
3 [(1,), (3,), (2, 4)]
3 [(1,), (4,), (2, 3)]
3 [(2,), (3,), (1, 4)]
3 [(2,), (4,), (1, 3)]
3 [(3,), (4,), (1, 2)]
4 [(1,), (2,), (3,), (4,)]
小智 5
最简单的选择是使用more_itertools库。
from more_itertools import set_partitions
a = [1, 2, 3, 4]
# pass as the second argument the number of splits
list(set_patitions(a, 2))
...
[[[1], [2, 3, 4]],
[[1, 2], [3, 4]],
[[2], [1, 3, 4]],
[[1, 2, 3], [4]],
[[2, 3], [1, 4]],
[[1, 3], [2, 4]],
[[3], [1, 2, 4]]]
>>>
list(set_patitions(a, 3))
...
[[[1], [2], [3, 4]],
[[1], [2, 3], [4]],
[[1], [3], [2, 4]],
[[1, 2], [3], [4]],
[[2], [1, 3], [4]],
[[2], [3], [1, 4]]]
>>>
set_partitions 使用生成器，允许立即创建数千个集合。