将 N 个唯一元素放入所有可能的 K 组中，并保持单调性

Question

谁能提出一个快速有效的解决方案，将 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]

我可以通过详尽的搜索和大量检查来解决这个问题，但是如果有人已经解决了类似的问题并且可以提出更有效的方法或一些想法来开始怎么办？

Answer 1

基本上，您需要找出组合，以便从 len(mas) - 1 个可能的位置中选择 K-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]]]

Answer 2

如果我们可以为每个列表生成所有可能的有效长度，那么我们可以生成这些长度，然后使用列表切片将其读出到我们的结果中。

更具体地说，我们需要生成所有可能的正整数排列，使它们的总和等于要分区的列表的长度。

这个问题的一个小变体恰好是 asked on Whosebug in 2011. (This variant merely required that all the numbers be non-negative, rather than strictly positive.) Using the code from this answer 稍作修改，我们可以生成所需的排列，然后将它们读入我们的最终结果：

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() 从 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]]
]

将 N 个唯一元素放入所有可能的 K 组中，并保持单调性

Place N unique elements into all possible K groups with monotonicity maintaining

python

algorithm

list

combinatorics