时间戳

首页 > 解决方案 > 具有 16 个整数的列表的排列，但前提是满足 4 个条件

python - 具有 16 个整数的列表的排列，但前提是满足 4 个条件

问题描述

我有一个整数列表

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

我想找到这个列表的所有排列，这样对于每个排列

  1. 元素 0 到 3 加起来为 264，

  2. 元素 4 到 7 加起来为 264，

  3. 元素 8 到 11 加起来是 264 和

  4. 元素 12 到 15 到 264。

目前我有以下策略

  1. 使用 itertools.permutations 计算所有排列

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

还有其他性能更好的策略吗？

标签： pythoncombinationspermutationconstraint-satisfaction

解决方案

好的，这是有关如何执行此操作的初步想法。它生成所有总和为 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)

推荐阅读