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

6
votes

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?

4
pythoncombinationspermutationconstraint-satisfaction
I realize that my question could have been asked in a better way. I've made an update. @ChrisDoyle – Olba12
please don't close this, i am working on a solution. – Christian Sloper
In my view, calculating all the permutations then checking which satisfy s, will be around the same speed as generating a single permutation and checking if it meets the criteria. then generating the next. You will still have to go through N permutationsa dn N calculations – Chris Doyle
Could you please comment ony why you think the question focus on more than one problem? @jonrsharpe – Olba12
Try this, it's awesome, i was two seconds away from adding this as an answer before it was closed. it's really cool and wanted to share it, you just need to pip install more_itertools: from more_itertools import distinct_combinations import numpy as np np.array(list(distinct_combinations(keys,4)))[[sum(x)==264 for x in distinct_combinations(keys,4)]] – oppressionslayer

4 Answers

3
votes

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)
1
votes

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

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

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)