Python

Question

我有 2 个列表，一个有 12 个元素，一个有 3 个子列表。

a = [1,2,3,4,5,6,7,8,9,10,11,12]
b = [[],[],[]]

我需要编写 Python 代码来生成所有可能的方式，使 a 中的 12 个元素可以分布在 b 中的子列表中。有 3^12（刚刚超过 50 万）种组合。例如，一些可能的组合如下：

[[1,2,3,4,5,6,7,8,9,10,11,12],[],[]]
[[1,2,3,4],[5,6],[7,8,9,10,11,12]]
[[1,4,12],[2,3,9,11],[5,6,7,8,10]]

列表中的顺序无关紧要。我已经尝试使用一些 itertools 函数，例如排列和组合，但它们似乎无法满足我的需求。我试过了

    buildings = list(range(1,13)) #assign each building a unique id
    building_arrangement = [list(range(1,13)),[],[]] # quarries, factories, markets
    all_arrangements.append(building_arrangement)
    
    combos = itertools.combinations(buildings, 3)
    
    for combo in combos:
        print(combo)

但上面的方法似乎是单独获得 12 个数字中的每一个的组合，而不是将完整的 12 个数字视为一个集合并找到可以制作的每个唯一集合。我不确定这是否可以通过任何预先存在的库来完成，从我在文档中看到的内容，itertools 似乎没有提供这样做的方法，但我可能是错的。

Answer 1

您可以使用递归生成器函数：

a = [1,2,3,4,5,6,7,8,9,10,11,12]
def groups(d, n, c = []):
   if not d and len(c) == n:
      yield c
   elif d:
      for i, j in enumerate(d):
         if not c or len(c) + 1 <= n:
            yield from groups(d[:i]+d[i+1:], n, c+[[j]])
         if c:
            yield from groups(d[:i]+d[i+1:], n, c[:-1]+[[*c[-1], j]])

def results(d, n):
    s = []
    for i in groups(d, n):
       if (k:=[*map(sorted, i)]) not in s:
          yield k
          s.append(k)

r = results(a, 3)
for _ in range(10): #first 10 results
   print(next(r))

输出：

[[1], [2], [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3], [4, 5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4], [5, 6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5], [6, 7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7], [8, 9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8], [9, 10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9], [10, 11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12]]
[[1], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [12]]

Answer 2

请注意，每个组合都可以用 m 进制数编码，其中 m 是子列表的数量。迭代所有 n 位 m 进制数（其中 n 是元素的数量）将达到目的：

N = 12
M = 3

for n in range(N**M):
    combination = [[] for __ in range(M)]
    for i in range(N):
        combination[n // 3**i % 3].append(i)
    print(combination)

Answer 3

另外为什么不尝试 itertool recipes、powerset()

pip install more-itertools

然后，

from more_itertools import recipes

a = [1,2,3,4,5,6,7,8,9,10,11,12]
tuples = recipes.powerset(a)
for tuple in tuples:
  print(tuple)

这将从给定的可迭代对象创建所有可能的集合。您可以使用不同的函数将其分成 3 个列表。

Python - 如何以各种可能的方式生成 12 个项目的列表可以分成 3 个任意大小的列表（包括空列表）

Python - How to generate every possible way a list of 12 items can be split into 3 lists of any size (including empty)

arrays

list

combinations