我需要创建一个包含 4 组 3 个数字的所有可能集合的列表，因此每组集合将有 12 个数字 (4 * 3 = 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))
另一个是
((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12))
所以这两个集合应该位于排列数组内。排列数组应该看起来像
(((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12)), (((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12)), ...)
当然，“...”意味着还有更多的组集。
但是，顺序确实很重要。正因为如此，
((6, 4, 3), (7, 1, 5), (11, 2, 8), (9, 12, 10))
和
((9, 10, 12), (2, 11, 8), (1, 7, 5), (3, 6, 4))
两者相同
((4, 3, 6), (1, 5, 7), (2, 8, 11), (9, 10, 12))
具体来说，如果组的顺序或组内事物的顺序不同，它仍然是同一组组。
实现此目的的一种方法是执行 12 个嵌套 for 循环 (3 * 4 = 12)，但我正在寻找使用内置函数来代替。有人可以帮忙吗？
注意：我用括号将括号数组设置为二维元组，每个组设置一个一维元组，但它不一定是元组。可以是列表、列表[元组]、元组[列表]等
注 2：我希望时间复杂度最多为 O(N!)，在本例中，N = 12。
注∞：这是为了解决平衡团队。
这是一种方法：使用 itertools.combinations 将东西切成两半，然后再次使用它将这些东西切成两半。
from itertools import combinations, product
def splittings(numbers):
numbers = frozenset(numbers)
assert len(numbers) == 12
result = set()
for AB in map(frozenset, combinations(numbers, 6)):
CD = numbers - AB
first_half_splittings = []
for A in map(frozenset, combinations(AB, 3)):
B = AB - A
first_half_splittings.append((A, B))
second_half_splittings = []
for C in map(frozenset, combinations(CD, 3)):
D = CD - C
second_half_splittings.append((C, D))
for A_B, C_D in product(first_half_splittings, second_half_splittings):
result.add(frozenset(A_B + C_D))
return [tuple(map(tuple, splitting)) for splitting in result]
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for split in splittings(numbers):
print(split)
这最终会导致每次分割过度计数 4!=24 次，但这可以使用一组冻结集来解决。
这里可能还有更多的优化，例如，总是将第一个值分配给第一个 bin，然后将剩余的 11 分成 5+6。但这应该是一个不错的起点。
编辑：这是此类优化的实现，它使事情在我看来更容易理解。
from itertools import combinations, product, starmap
from operator import add
def pair_splittings(numbers, k):
n0, *rest = numbers
rest = frozenset(rest)
for B in combinations(rest, len(numbers) - k):
A = (n0,) + tuple(rest - frozenset(B))
yield (A, B)
def splittings(numbers):
assert len(numbers) == 12
for AB, CD in pair_splittings(numbers, 6):
first_halves = pair_splittings(AB, 3)
second_halves = pair_splittings(CD, 3)
half_choices = product(first_halves, second_halves)
yield from starmap(add, half_choices)
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
for split in splittings(numbers):
print(split)
Edit2：一个更通用的解决方案，可推广到不同数量的垃圾箱。
from itertools import combinations, product, starmap
from operator import add
def pair_splittings(numbers, k):
n0, *rest = numbers
rest = frozenset(rest)
for B in combinations(rest, len(numbers) - k):
A = (n0,) + tuple(rest - frozenset(B))
yield (A, B)
def splittings(elements, num_bins):
assert len(elements) % num_bins == 0
bin_size = len(elements) // num_bins
if num_bins == 1:
yield (tuple(elements),)
return
k = num_bins // 2
for half1, half2 in pair_splittings(elements, k*bin_size):
# Option 1: a little bit eager. ##############################
# Here, product() stores both sequences that it's
# iterating through. This is much faster than re-computing
# half2_splittings over and over. Note that storing both
# halves is much less memory than storing their entire product,
# so this is still somewhat lazy.
half1_splittings = splittings(half1, k)
half2_splittings = splittings(half2, num_bins-k)
half_choices = product(half1_splittings, half2_splittings)
yield from starmap(add, half_choices)
# Option 2: extra-lazy. ##############################
# If you're dealing with bigger numbers and minimal memory,
# this might be a better aproach.
# for choices1 in splittings(half1, k):
# for choices2 in splittings(half2, num_bins-k):
# yield choices1 + choices2
for x in splittings(range(12), 4):
print(x)