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

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