生成所有可能的分割

我正在尋找以下任務中最快的算法。我有一些陣生成所有可能的分割

[A，B，C ...]

，我需要生成陣列的一些同樣隨機數組，其中包含主陣列中的所有元素，像這樣：

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

Straitforward解決方案是生成所有分割並隨機選擇其中之一。這個解決方案保證所有的分裂將以相等的概率進行選擇。但是對於大數字來說它太慢了。有沒有其他的可能性來創造這種分裂？

來源

2016-01-23 Oleg

您是否必須在開始時拆分項目？如果不是，你可以在需要時做到。它可以節省空間和時間。假設你必須使用3元素的子陣列來分割數組，當你需要一些隨機元素時，你可以生成'x = rand％（n/3）'並獲取'x * 3'，'x * 3 + 1'，'x * 3 + 2'。這僅僅是一個解決方案，一開始就不需要它們。 – meth

對於每個可能的分裂點，隨機決定是否在那裏分裂。例如，在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

來源

2016-01-23 22:09:19 user2357112

這有利於許多分割（按照「N/2」的順序，其中'N'是列表長度），即它在所有分割的空間中是不統一的。 – davidhigh

@davidhigh：但這正是你所期望的統一分配。你可以很容易地看到分裂的平均分裂數是（N-1）/ 2，因爲每個可能的分裂對應於第二次分裂，在第一次分裂沒有分裂的地方，你不會分裂第一個分裂分裂了。 – user2357112

重新思考一遍，我認爲你是對的（我的直覺錯了）。 – davidhigh

生成所有可能的分割

回答

相關問題