如何找到列表的所有可能分解成大小大于 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]]];

直到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 在只有两个项目的集合中时。要找到这些组合，我们需要 select 其余 N-1 项之一，并将 selected 项与项 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

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

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

python

combinations

list

combinatorics