How to find a list of all possible decompositions of a list into chunks of size bigger than 2

Question

For a given N, I have a list of all numbers from 0 to N-1

A = list(range(0,N));

and I want to find a list of all possible decompositions into lists of sizes two or higher, without repetitions. For example, for N=4 I have

A = [0,1,2,3];

and the output I want is

OUT = [[[0, 1, 2, 3]], [[0, 1], [2, 3]], [[0, 2], [1, 3]], [[0, 3], [1, 2]]];

Up to N=5, the decomposition of the initial list into only two pieces (of length 2 and 3) makes the problem very easy. However, I can't find a way to do it for higher N, since the lists of length four must be further split into two lists of length 2.

Does anyone have any suggestions on how to solve this? I feel there must be a straightforward recursive trick to do this, but I have been trying for a day now, and I am a little stuck!

Thanks!

PS: the results for N smaller than 6 are:

N=1) OUT = [[[0]]];
N=2) OUT = [[[0, 1]]];
N=3) OUT = [[[0, 1, 2]]];
N=4) OUT = [[[0, 1, 2, 3]], [[0, 1], [2, 3]], [[0, 2], [1, 3]], [[0, 3], [1, 2]]];
N=5) OUT = [[[0, 1, 2, 3, 4]], [[0, 1], [2, 3, 4]], [[0, 2], [1, 3, 4]], [[0, 3], [1, 2, 4]], [[0, 4], [1, 2, 3]], [[1, 2], [0, 3, 4]], [[1, 3], [0, 2, 4]], [[1, 4], [0, 2, 3]], [[2, 3], [0, 1, 4]], [[2, 4], [0, 1, 3]], [[3, 4], [0, 1, 2]]];

PPS: I am a physicist and haven't been programming for a while; the code probably looks terrible, and the problem might be very easy... sorry for that!

Answer 1

Consider the last item i.e N-1, suppose we have two sets of combinations. one for list(range(0,N-1)) and one for list(range(0,N-2)). Now, if you want to put the last item in these combinations, you should have a different approach for each one of them, which I've explained below:

• Combinations of list(range(0, N-1)): To put the last item in these combinations, you have no choice other than to put it in one of the sets that are already available to understand this better consider that you have all combinations for four and now you want to add 5 to this combination. So you have :

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

  Adding last item( i.e 4) to these combination would get us something like bellow:

  [[[0, 1, 2, 3, 4]], [[0, 1, 4], [2, 3]], [[0, 1], [2, 3, 4]], [[0, 2, 4], [1, 3]], [[0, 2], [1, 3, 4]], [[0, 3, 4], [1, 2]], [[0, 3], [1, 2, 4]]]

  We put 4 in every combination and make new combinations out of them. So for this part, we need a recursive call for N-1. As you can see in this situation, each sets that N-1 is in has at least three items. That's because we expanded our set, which already existed and had at least two items.

• Combinations of N-2 items: I've considered this for when N-1 is in a set with only two items. To find these combinations, we need to select one of the rest N-1 items and consider that selected item with item N-1 as one set and find every other combination for the rest of N-2 items. To give you an example again, consider N = 5 so the last item is 4. If we want to pair the last item with 3, we could build all combinations for (0, 1, 2) and put pair of the (3, 4) to the mix. It would be something like this for N=5:

  [[[0 , 1 , 2] , [3 , 4]] , [[0 , 1 , 3] , [2 , 4]] , [[0 , 2 , 3] , [1 , 4]] , [[ 1 , 2 , 3] , [0 , 4]]]

I've implemented this using recursive functions in python. I'm not a python developer, so there may be some enhancements in implementations, but the algorithm is working fine:

import copy

def recursive_builder(arr):
  if len(arr) == 3:
    return [[[arr[0], arr[1], arr[2]]]]
  if len(arr) == 4:
    return [[[arr[0], arr[1], arr[2], arr[3]]], [[arr[0], arr[1]], [arr[2], arr[3]]], [[arr[0], arr[2]], [arr[1], arr[3]]], [[arr[0], arr[3]], [arr[1], arr[2]]]]
  temp_array = arr[0:len(arr)-1]
  recursive_builder_one_step_before = recursive_builder(temp_array)
  new_from_one_step_before = []
  last_item = arr[len(arr)-1]
  for item in recursive_builder_one_step_before:
    for i in range(0 , len(item)):
      temp_item = copy.deepcopy(item)
      temp_item[i].append(last_item)
      new_from_one_step_before.append(temp_item)
  new_from_two_step_before = []
  for i in range(0 , len(temp_array)):
    new_arr = temp_array[:i] + temp_array[i+1 :]
    recursive_builder_two_step_before = recursive_builder(new_arr)
    new_from_two_step_before_inner = []

    for item in recursive_builder_two_step_before:
      new_item = item + [[temp_array[i] , last_item]]
      new_from_two_step_before_inner.append(new_item)

    new_from_two_step_before = new_from_two_step_before + new_from_two_step_before_inner
    
  return new_from_two_step_before + new_from_one_step_before


N=6
recursive_builder(list(range(0,N)))

You could run this code on Colab

Edit: I've added memorization to improve the performance a little bit, but my build_from_memory is not O(1), so the improvement could be much better if I could improve the performance of that function.

memotization_dict = {3 : [[[0, 1, 2]]] , 4 : [[[0, 1, 2, 3]], [[0, 1], [2, 3]], [[0, 2], [1, 3]], [[0, 3], [1, 2]]] }
def build_from_memory(arr):
  memory = memotization_dict[len(arr)]
  ret_val = []
  for item in memory:
    l2 = []
    for i in item:
      l1 = []
      for j in i:
        l1.append(arr[j])
      l2.append(l1)
    ret_val.append(l2)

  return ret_val

def recursive_builder(arr):
  if len(arr) in memotization_dict:
    return build_from_memory(arr)
  temp_array = arr[0:len(arr)-1]
  recursive_builder_one_step_before = recursive_builder(temp_array)
  new_from_one_step_before = []
  last_item = arr[len(arr)-1]
  for item in recursive_builder_one_step_before:
    for i in range(0 , len(item)):
      temp_item = copy.deepcopy(item)
      temp_item[i].append(last_item)
      new_from_one_step_before.append(temp_item)
  new_from_two_step_before = []
  for i in range(0 , len(temp_array)):
    new_arr = temp_array[:i] + temp_array[i+1 :]
    recursive_builder_two_step_before = recursive_builder(new_arr)
    new_from_two_step_before_inner = []

    for item in recursive_builder_two_step_before:
      new_item = item + [[temp_array[i] , last_item]]
      new_from_two_step_before_inner.append(new_item)

    new_from_two_step_before = new_from_two_step_before + new_from_two_step_before_inner
    
  if(arr == list(range(0 , len(arr)))):
    memotization_dict[len(arr)] = new_from_two_step_before + new_from_one_step_before
  return   new_from_two_step_before + new_from_one_step_before