python - 具有 16 个整数的列表的排列，但仅当满足 4 个条件时

Question

我有一个整数列表

keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96]

我想找到 的所有排列此 列表使得对于每个排列

元素 0 到 3 加起来为 264，

元素 4 到 7 加起来为 264，

元素 8 到 11 加起来为 264 和

元素 12 到 15 广告最多 264。

目前我有以下策略

使用 itertools.permutations

计算所有排列

检查哪些排列满足我的条件

是否有另一种性能更好的策略？

Answer 1

好的，这是如何做到这一点的初步想法。它生成总和为 264 的 4x4 子集集的组合(只有 675 个这样的有序组合)。

接下来，您需要对 25 种组合中的每一种中的 4 组中的每组进行排列。这应该会产生大约 2.24 亿个解决方案。这种方式比您的蛮力生成和检查快约 90 000 倍。

from itertools import combinations

keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96]
keys_set = set(keys)

def f(key_set):

    for i in combinations(keys_set,4):
        if sum(i) == 264:
            rem_set = keys_set - set(i)
            for j in combinations(rem_set,4):
                if sum(j) == 264:
                    rem_set2 = rem_set - set(j)
                    for k in combinations(rem_set2,4):
                        if sum(k) == 264:
                            rem_set3 = rem_set2 - set(k)
                            if sum(rem_set3) == 264:
                                yield i,k,j,rem_set3

for i,k,j,l in f(keys_set):
     for a in product(permutations(i), permutations(j), permutations(k), permutations(l)):
        print(a)

我为丑陋的代码道歉，但我认为在问题结束之前获得解决方案很重要。下面是一个更简洁的版本。

def g(key_set):
    for i in combinations(key_set,4):
        if sum(i) == 264:
            yield i, key_set- set(i)

def g2(key_set):
    for i, r in g(key_set):
        for j, r2 in g(r):
            for k, r3 in g(r2):
                for l, r in g(r3):
                    yield i,j,k,l



for i,j,k,l in g2(keys_set):
    for a in product(permutations(i), permutations(j), permutations(k), permutations(l)):
        print(a)