生成所有可能的分裂

Question

我正在为以下任务寻找最快的算法。我有一些数组

[a,b,c ...]

我需要生成一些同样随机的数组，其中包含主数组的所有元素，如下所示：

Input [1 2 3 4 5 ] => [ [1 2 ] [3 4 ] [ 5 ] ]

Straitforward 解决方案是生成所有拆分并随机选择其中一个。该解决方案保证将以相等的概率选择所有拆分。但是对于大数字来说太慢了。是否有其他可能创建此拆分？

Answer 1

对于每个可能的分裂点，随机决定是否在那里分裂。例如，在 Python:

import random

def random_split(input_list):
    result = [[]]

    # Assume input is nonempty, since it's not clear what the result should
    # be if the input is empty.
    result[-1].append(input_list[0])

    for item in input_list[1:]:
        if random.randrange(2):
            # Split here.
            result.append([])
        result[-1].append(item)

    return result

生成所有可能的分裂

Generate all possible splittings

algorithm

combinations

combinatorics