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

问题描述 投票：5回答：4

我有一个整数列表

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

我想找到this列表的所有排列，以便每个排列

  1. 元素0到3总计为264，

  2. 元素4至7总计为264，

  3. 元素8到11总计为264和

  4. 元素12到15，最多264个。

当前我有以下策略

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

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

还有另一种效果更好的策略吗？

python combinations permutation constraint-satisfaction
4个回答
2
投票

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

接下来，您需要对25个组合中的每一个中的4组中的每组进行置换。这将产生大约2.24亿个解决方案。这种方法比蛮力生成和检查的速度快90000倍。

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)
1
投票

您可以对生成器使用递归：

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所需的次数以访问产生的结果：

for _ in range(100):
   print(next(l, None))

输出：

 [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]
 ...
0
投票

有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

输出：

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

这应该快一点，因为我限制了从中得到组合的元素的数量（我只称一次组合）。这也利用了keys的唯一性：

import itertools
import numpy as np
def foo():
    keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96]
    n=4
    s=264
    lst=[el for el in itertools.combinations(keys, n) if sum(el)==s]
    for el in itertools.product(lst,repeat=4):
        if len(set(np.array(el).ravel()))==16:
            yield np.array(el).ravel()

for el in foo():
    print(el)

输出：

[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 89 68 69 88 11 96]
[18 99 86 61 66 81 98 19 69 88 11 96 91 16 89 68]
[18 99 86 61 66 81 98 19 89 68 11 96 91 16 69 88]
[18 99 86 61 66 98 89 11 81 19 68 96 91 16 69 88]
[18 99 86 61 66 98 89 11 91 16 69 88 81 19 68 96]
[18 99 86 61 66 19 91 88 81 98 16 69 89 68 11 96]
[18 99 86 61 66 19 91 88 89 68 11 96 81 98 16 69]
...

（（如果希望将结果保留为四个四元素元组的格式，则可以在行.ravel()中删除yield）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.