如何獲得至少一定大小的列表分組的所有組合？

Question

給定一個列表（或Java，我試圖在兩種語言中都這樣做），我怎麼能得到所有不同的方式來分割一個列表到不同的分組，因爲每個分組必須至少有一定的大小？我認爲獲得拆分地點的組合是最好的方式。

列表和最小尺寸的示例輸入是

[1,2,3], 2 

和相應的輸出應是

[[1,2], [1,3], [2,3], [1,2,3]] 

Answer 1

編輯

基於OP的新的輸入/輸出要求，它只是幾行：

def groupings(lst, min_size): 
    results = [tuple(lst)] 
    for i in range(min_size, len(lst)): 
     results.extend(combinations(lst, i)) 
    return results 

ORIGINAL

（基於不正確的假設，OP通緝給定最小分區大小的所有可能的分區）。

所以itertools.combinations（）應該是一個起點。例如，

>>> list(combinations('ABCD', 2)) 
[('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')] 

這樣就給出了一個答案。您的分組與最小大小設置爲2「ABCD」的輸出是：

[['A', 'B', 'C', 'D']] 
[['A', 'D'], ['B', 'C']] 
[['A', 'C'], ['B', 'D']] 
[['A', 'B'], ['C', 'D']] 

所以高層次的過程應該是大致爲：

results = [] 
remaining = [([], list)] # Start without any groups and the full list 

while remaining not empty: 

    groups, list = remaining.pop() 

    if len(list) >= min_size: 
     results.append(groups + list) 

    for size in min_size to len(list) - 1: 

     for combo in combinations: 
      new <- (groups + combo, list - combo) 

      if new will not cause duplicates: 
       remaining.append(new) 

下面是一些代碼，似乎工作。爲了避免重複，並處理原始列表可能有重複的情況，我修改了itertools.combinations中的代碼，而不僅僅是使用方法。

def groupings(lst, min_size): 

    lst = list(lst) 

    # List for storing our final groupings 
    results = [] 

    # Unfinished grouping, tuple storing the group and remaining sub-list 
    # Initialize with the empty group and original list 
    remaining = [([], lst)] 

    # Continue as long as we have unfinished groupings 
    while len(remaining): 

     # Get an unfinished grouping 
     current_group, current_lst = remaining.pop() 
     n = len(current_lst) 

     # If the last part of the list is big enough, 
     # then record the grouping 
     if n >= min_size: 
      results.append(current_group + [current_lst]) 

     # Otherwise, discard it 
     else: 
      continue 

     # Helper set for getting remainder below 
     all_indices = set(range(n)) 

     # Iterate the group length from min_size to the length of our current list 
     for r in range(min_size, n - 1): 

      # This is a modified version of itertools.combinations() 
      # http://docs.python.org/3.3/library/itertools.html#itertools.combinations 

      # Add the first combination to our remaining list 
      indices = list(range(r)) 
      remainder = current_lst[r:] 
      group = current_group + [current_lst[:r]] 
      remaining.append((group, remainder)) 

      while True: 
       for i in reversed(range(r)): 
        if indices[i] != i + n - r: 
         break 
       else: 
        break 

       indices[i] += 1 
       for j in range(i+1, r): 
        indices[j] = indices[j-1] + 1 

       # If one of the remaining indexes is less than the minimum used index, 
       # then a different iteration will handle it, so discard this one 
       min_index = min(indices) 
       remainder = [] 
       for i in all_indices.difference(indices): 
        remainder.append(current_lst[i]) 
        if i < min_index: 
         break 
       else: 
        # Add this combination to our remaining list 
        group = current_group + [[current_lst[i] for i in indices]] 
        remaining.append((group, remainder)) 

    return results 

結果：

>>> groupings('ABCDE', 2) 
[['A', 'B', 'C', 'D', 'E']] 
[['A', 'D', 'E'], ['B', 'C']] 
[['A', 'C', 'E'], ['B', 'D']] 
[['A', 'C', 'D'], ['B', 'E']] 
[['A', 'B', 'E'], ['C', 'D']] 
[['A', 'B', 'D'], ['C', 'E']] 
[['A', 'B', 'C'], ['D', 'E']] 
[['A', 'E'], ['B', 'C', 'D']] 
[['A', 'D'], ['B', 'C', 'E']] 
[['A', 'C'], ['B', 'D', 'E']] 
[['A', 'B'], ['C', 'D', 'E']] 

Answer 2

在Python，可以做到這一點遞歸：

def partition(lst, minsize=1): 
    yield [lst] 
    for n in range(minsize, len(lst)-minsize+1): 
     for p in partition(lst[n:], minsize): 
      yield [lst[:n]] + [l for l in p] 

例如：

>>> lst = [1, 2, 3, 4, 5, 6, 7] 
>>> partition(lst, 3) 
[[[1, 2, 3, 4, 5, 6, 7]], 
[[1, 2, 3], [4, 5, 6, 7]], 
[[1, 2, 3, 4], [5, 6, 7]]] 
>>> list(partition(lst, 2)) 
[[[1, 2, 3, 4, 5, 6, 7]], [[1, 2], [3, 4, 5, 6, 7]], 
[[1, 2], [3, 4], [5, 6, 7]], [[1, 2], [3, 4, 5], [6, 7]], 
[[1, 2, 3], [4, 5, 6, 7]], [[1, 2, 3], [4, 5], [6, 7]], 
[[1, 2, 3, 4], [5, 6, 7]], [[1, 2, 3, 4, 5], [6, 7]]]