有16个整数的列表的置换，但仅当满足4个条件时

Question

我有一个整数列表

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.排列

2. 满足mycheck的条件

有没有其他更好的策略？在

Answer 1

好的，这里有一个初步的想法。它生成4x4个子集集合的组合，这些子集的总和为264（只有675个这样的有序组合）。在

接下来，你需要对25个组合中的4个集合进行排列。这将产生大约2.24亿个解决方案。这种方法比你的暴力生成和检查快9万倍。在

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)

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

^{pr2}$

Answer 2

这些数字有672个唯一的组合，符合标准。我没有在这些独特的组合中进行置换，因为我认为这是一个我没有的计算周期的练习：-）。这是672个4x4数字的独特组合，等于264。如果你想在这些独特的组合中进行排列，数量会大大增加，但我认为重要的是展示出完成任务可能的独特组合。在

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

import itertools
unique_data = np.array(list(itertools.combinations(keys,4)))[[sum(x)==264 for x in itertools.combinations(keys,4)]]

i=0 
for w in unique_data: 
 for x in unique_data: 
  for y in unique_data: 
    for z in unique_data:    
      if len(set(x)|set(y)|set(w)|set(z))==16: 
        print(x,y,w,z) 
        i+=1 

输出：

^{pr2}$

Answer 3

可以对生成器使用递归：

keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96]
req = {(0, 3): 264, (4, 7): 264, (8, 11): 264, (12, 15): 264}
def combos(d, c = []):
  if len(d) == len(c):
     yield c
  else:
     for i in filter(lambda x:x not in c, d):
        if all(sum(_k[a:b+1]) == j if len((_k:=(c+[i]))) == b+1 else sum(_k[a:b+1]) <= j for (a, b), j in req.items()):
          yield from combos(d, _k)


l = combos(keys)

由于有大量可能的组合，如果您尝试将所有生成器值加载到一个列表中，即list(combos(keys))，此解决方案将挂起。但是，您可以在l上重复一定次数以访问生成的结果：

^{pr2}$

输出：

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