如何找到将列表分解为大小大于 2 的块的所有可能分解的列表

Question

对于给定的 N，我有一个从 0 到 N-1 的所有数字的列表

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

，并且我想找到所有可能分解为大小为 2 或更大的列表的列表，而不重复。例如，对于 N=4 我有

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

并且我想要的输出是

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

Up to N=5，将初始列表分解为仅两部分（长度为 2 和 3）使问题变得非常简单。但是，我找不到一种方法来实现更高的 N，因为长度为 4 的列表必须进一步分成两个长度为 2 的列表。

有谁对如何解决这个问题有任何建议吗？我觉得一定有一个简单的递归技巧来做到这一点，但我已经尝试了一天了，我有点卡住了！

谢谢！

PS：N小于6的结果是：

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：我是一名物理学家，有一段时间没有编程了；代码可能看起来很糟糕，而且问题可能很简单......对此感到抱歉！

Answer 1

考虑最后一项，即 N-1，假设我们有两组组合。一种用于 list(range(0,N-1))，另一种用于 list(range(0,N-2))。现在，如果您想将最后一项放入这些组合中，则应该对每个组合采用不同的方法，我在下面对此进行了解释：

• list(range(0, N-1))：要将最后一个项目放入这些组合中，您别无选择，只能将其放入已经可用的集合之一中，以便更好地理解这一点，考虑到您拥有所有四个组合，现在您想向此组合添加 5 个。所以你有：

  <代码>[[[0, 1, 2, 3]], [[0, 1], [2, 3]], [[0, 2], [1, 3]], [[0 , 3], [1, 2]]]

  将最后一项（即 4）添加到这些组合中将使我们得到如下所示的结果：

  <代码>[[[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]]]

  我们在每个组合中放入 4 个，并用它们组成新的组合。因此，对于这一部分，我们需要对 N-1 进行递归调用。正如您在这种情况下所看到的，N-1 所在的每个集合至少包含三个项目。这是因为我们扩展了我们的集合，该集合已经存在并且至少有两个项目。

• N-2 项的组合：当 N-1 位于只有两项的集合中时，我考虑过这种情况。要找到这些组合，我们需要选择其余 N-1 项中的一项，并将该选定项与项 N-1 视为一组，并找到所有其他组合其余的 N-2 项。再次举个例子，请考虑 N = 5，因此最后一项是 4。如果我们想将最后一个项目与 3 配对，我们可以构建 (0, 1, 2) 的所有组合，并将 (3, 4 ） 来混合。 N=5 的情况如下：

  <代码>[[[0 , 1 , 2] , [3 , 4]] , [[0 , 1 , 3] , [2 , 4]] , [[0 , 2 , 3] , [1 , 4]] , [[ 1 , 2 , 3] , [0 , 4]]]

我已经使用 python 中的递归函数实现了这一点。我不是 python 开发人员，因此实现中可能有一些增强，但算法工作正常：

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)))

您可以在 Colab

编辑：我已添加记忆稍微提高了性能，但我的 build_from_memory 不是 O(1)，所以如果我可以提高该函数的性能，改进可能会更好。

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