Permutations of a list with 16 integers but only if 4 conditions are fulfilled

Question

I have a list of integers

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

I'd like to find all permatutations of this list such that for each permutation

1. elements 0 through 3 add up to 264,

2. elements 4 through 7 add up to 264,

3. elements 8 through 11 add up to 264 and

4. elements 12 through 15 ad up to 264.

Currently I have the following strategy

1. Calculate all permutations using itertools.permutations

2. Check which of the permutations satisfy my conditions

Is there another strategy with better performance?

Answer 1

You can use recursion with a generator:

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)

Due to the large number of possible combinations, this solution will hang if you try to load all the generator values into a list i.e list(combos(keys)). However, you can iterate over l a desired number of times to access the produced results:

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

Output:

 [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]
 ...

Answer 2

This should be a bit faster, since I limited number of elements we get combinations from (I call combination just once). This is leveraging uniqueness of keys too:

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)

Output:

[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]
...

(You can remove .ravel() in the line, where I yield, if you wish to keep the result in a format of four four-elements tuples)

Answer 3

Ok, here is an initial idea of how to do it. It generates the combinations of 4x4 sets of subsets that all sum to 264 (there are only 675 such ordered combinations).

Next you need to do a permutation for each of the 4 sets in each of 25 combinations. This should yield roughly 224 million solutions. This way is about 90 000 times faster than your brute force generation and check.

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)

I apologize for the ugly code, but i thought it was important to get in a solution before the question was closed. Below is a more concise version.

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)

Answer 4

There are 672 unique combinations of these numbers that match the criteria. I did not permute inside the unique combinations as i thought this an exercise in computing cycles i don't have :-). These are the 672 unique combinations of 4x4 numbers that equal 264. If you want to permute inside those unique combinations, the number expands monumentally, but i think the important part is showing the unique combinations possible to complete the task.

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 

output:

[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]
...