Создание всех возможных разделов

Question

Я ищу самый быстрый алгоритм для выполнения следующей задачи. У меня есть некоторый массив

[а, 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