任何人都可以提出一種快速有效的解決方案，將 N 個元素的陣列拆分為 K 個組并保持單調性嗎？例如：
mas = [1, 2, 3, 4, 5]
K = 3
預期輸出：
[1], [2], [3, 4, 5]
[1, 2], [3], [4, 5]
[1, 2, 3], [4], [5]
[1, 2], [3, 4], [5]
[1], [2, 3], [4, 5]
[1], [2, 3, 4], [5]
我可以通過詳盡的搜索和大量的檢查來解決這個問題，但是如果有人已經解決了類似的問題并且可以提出更有效的方法或一些想法開始呢？
uj5u.com熱心網友回復：
基本上，您需要找出K-1從所有可能位置中選擇位置的組合，即len(mas) - 1.
import itertools
# Data
mas = [1, 2, 3, 4, 5]
K = 3
ans = []
all_pos = list(range(1, len(mas)))
for pos in itertools.combinations(all_pos, K - 1):
tmp = []
prev_idx = 0
for curr_idx in pos:
tmp.append(mas[prev_idx:curr_idx])
prev_idx = curr_idx
tmp.append(mas[curr_idx:])
ans.append(tmp)
ans
# [[[1], [2], [3, 4, 5]],
# [[1], [2, 3], [4, 5]],
# [[1], [2, 3, 4], [5]],
# [[1, 2], [3], [4, 5]],
# [[1, 2], [3, 4], [5]],
# [[1, 2, 3], [4], [5]]]
uj5u.com熱心網友回復：
如果我們可以為每個串列生成所有可能的有效長度，那么我們可以生成這些長度，然后使用串列切片將其讀入我們的結果中。
更具體地說，我們需要生成所有可能的正整數排列，以便它們總和到要磁區的串列的長度。
2011 年在 StackOverflow 上碰巧提出了這個問題的一個小變體。（這個變體只要求所有數字都是非負數，而不是嚴格正數。）使用這個答案中的代碼稍作修改，我們可以生成所需的排列，然后將它們讀入我們的最終結果：
def sums(length, total_sum):
if total_sum == 0:
return
if length == 1:
yield (total_sum,)
else:
for value in range(1, total_sum 1):
for permutation in sums(length - 1, total_sum - value):
yield (value,) permutation
mas = [1, 2, 3, 4, 5]
K = 3
results = []
for lengths in sums(K, len(mas)):
slices = []
start = 0
for slice_length in lengths:
slices.append(mas[start:start slice_length])
start = slice_length
results.append(slices)
print(results)
accumulate()您可以通過使用和chain()from生成起始索引來使此代碼更簡潔itertools：
mas = [1, 2, 3, 4, 5]
K = 3
results = []
for lengths in sums(K, len(mas)):
slices = []
for start, slice_length in zip(chain([0], accumulate(lengths)), lengths):
slices.append(mas[start:start slice_length])
results.append(slices)
這些輸出：
[
[[1], [2], [3, 4, 5]],
[[1], [2, 3], [4, 5]],
[[1], [2, 3, 4], [5]],
[[1, 2], [3], [4, 5]],
[[1, 2], [3, 4], [5]],
[[1, 2, 3], [4], [5]]
]
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/468472.html
上一篇：深度優先搜索找到二叉樹的最大深度