所有分组排列内置函数

Question

我需要创建一个由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。

Answer 1

这是一种方法:用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中，但这应该是一个不错的起点。

编辑:下面是这样一个优化的实现，它使我们更容易理解IMO。

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)