我们可以使用来自
这个答案的基本递归算法,并对其进行修改,以产生特定长度的划分,而无需生成和过滤不需要的划分。
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 = []
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)
result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
result = sorted(result, key = lambda ps: (*map(len, ps), ps))
return result
这里涉及许多内容,让我来解释一下。
首先,我们从同一个上述递归算法出发,实现了一个过程化的自底向上(术语?)实现:
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 = []
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
的分区,则此方法会执行许多不必要的工作(即递归调用)。
请注意,在上面的函数中,分区的长度(即组数)在以下情况下增加:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
...被执行。因此,我们通过在该块上放置警戒来限制分区的大小,像这样:
def partitions(seq, k):
...
def generate_partitions(i):
...
if len(groups) < k:
groups.append([seq[i]])
yield from generate_partitions(i + 1)
groups.pop()
将新参数和代码行添加到partitions
函数中,仅会生成长度高达k
的分区。这几乎是我们想要的,然而问题在于for
循环仍会有时生成长度小于k
的分区。
为了修剪这些递归分支,我们需要仅在确保剩余元素足够扩展工作集至总共k
个组时才执行for
循环。剩余元素数量或尚未放入组中的元素数量为n-i
(或len(seq)-i
),k-len(groups)
是我们需要添加的新组的数量以产生有效的k分区。如果n-i<=k-len(groups)
,则我们不能将其浪费并将其添加到当前组中,我们必须创建一个新的组。
因此,我们只需向另一个递归分支添加另一道防护罢了:
def generate_partitions(i):
...
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()
完成以上步骤后,您现在拥有一个运作良好的k分区生成器。您可能可以进一步简化一些递归调用(例如,如果还剩下3个项目,我们需要再分为3组,则已经知道必须将每个项目拆分为单独的组),但我想展示这个函数作为基本算法的轻微修改来生成所有分区。
唯一剩下的任务是对结果进行排序。不幸的是,与其弄清楚如何直接按所需顺序生成分区(这是聪明的狗的练习),我选择了先生成,再进行排序的方式(有点取巧)。
def sorted_k_partitions(seq, k):
...
result = generate_partitions(0)
result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
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
代表“parts”的复数形式。该代码表示按元素长度(它们必须是序列本身)对一个序列进行排序,然后再按序列本身的字典序排序。这用于将分区彼此排序,例如,[(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,)]