python – 如何在组长度和组内元素的所有可能组合中将列表拆分为n个组？
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了python – 如何在组长度和组内元素的所有可能组合中将列表拆分为n个组？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6090字，纯文字阅读大概需要9分钟。
内容图文
我想在所有可能的组合中将列表拆分为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的组不感兴趣,并且组内的顺序无关紧要.
我发现了两个类似的问题,但他们并没有完全回答我的问题.
This问题将列表拆分为所有组合,其中每个组的长度为n(我发现@tokland的答案)特别有用).但是,我并不是要寻找所有组长度相同的组.
然后,this问题的第一步获得拆分位置的独特组合,将列表拆分为n组.但是,此处保留了列表顺序,并且未确定这些组中元素的唯一组合.
我正在寻找这两个问题的组合 – 列表在组长度的所有可能组合中分成n组,以及组内元素的组合.
解决方法:
我们可以使用this answer中的基本递归算法并对其进行修改以生成特定长度的分区,而无需生成和过滤掉不需要的分区.
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
这里有很多事情,所以让我解释一下.
首先,我们从同一个aforementioned recursive algorithm的程序性,自下而上(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)将项目放入工作集中的每个当前组(a.k.a部分)并递归; 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()
将新参数和该行添加到分区函数现在将使其仅生成长度最大为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,)]
内容总结
以上是互联网集市为您收集整理的python – 如何在组长度和组内元素的所有可能组合中将列表拆分为n个组？全部内容，希望文章能够帮你解决python – 如何在组长度和组内元素的所有可能组合中将列表拆分为n个组？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。