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

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 2

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