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

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?

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)

Find the Number of Permutations that satisfy the given condition in , The permutations which do not satisfy this condition are {2, 1, 3}, {3, 1, 2}. If arr[] = {1, 2, 2, 3, 4}, the maximum element 4 has only one occurrence and no Therefore, if N is the size of the array and M is the number of elements in the int x = 0;. // Loop to check the number of elements. // occurring twice. 6 Permutations of a list with 16 integers but only if 4 conditions are fulfilled Dec 25 '19 2 The difference between arrays in Java and C May 20 '16 1 Open a folder in bash, when the foldername contains a blank space Mar 24 '16

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

Intrinsic functions in Fortran 90, Array inquiry functions; 16. When an argument list contains several arguments the function can be Note that they are all only defined for floating point numbers, and not for integers. The values will be the approved ones, i.e. the values which fulfill the condition, and will be in the ordinary Fortran order. 7 Given a list of numbers, find all matrices such that each column and row sum up to 264 6 Correct way to add 22 to 4 to get 82 6 Permutations of a list with 16 integers but only if 4 conditions are fulfilled

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

Python Tutorial: Recursive Functions, Introduction into recursive thinking, recursion and recursive functions in Python. Recursion is not only a fundamental feature of natural language, but of the If a function definition satisfies the condition of recursion, we call this function a 1 -Create a list of integers from two to n: 2, 3, 4, , n 2-Start with a counter i set to 2, � If the elements can repeat in the permutation, the formula is: In both formulas "!" denotes the factorial operation: multiplying the sequence of integers from 1 up to that number. For example, a factorial of 4 is 4! = 4 x 3 x 2 x 1 = 24. Permutation with repetition. In some cases, repetition of the same element is allowed in the permutation.

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)

Permutation, In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into It contains the first use of permutations and combinations, to list all possible (It is typical to use commas to separate these entries only if some have two or Here (file) is a list of these matrices for permutations of 4 elements. Now in this permutation (where elements are 2, 3 and 4), we need to make the permutations of 3 and 4 first. And thus, permutation(2,3) will be called to do so. Similarly, permutation(3,3) will be called at the end. At this point, we have to make the permutations of only one digit with the index 3 and it has only one permutation i.e., itself.

Permuting matrices to avoid forbidden submatrices, Finally, M is in .~c(~-) if and only if there exists a permutation ~ of the columns sequence for the matrix M if the following condition is fulfilled: For every 1 ~< i,� Permutations and combinations, the various ways in which objects from a set may be selected, generally without replacement, to form subsets. This selection of subsets is called a permutation when the order of selection is a factor, a combination when order is not a factor.

GAP (ref), If one has a list of group generators and is interested in the moved points (see above) or For the special case of the action of permutations on positive integers via ^ , the (1,12)(2,16)(3,19)(4,5)(6,22)(7,8)(9,23)(10,11)(13,24)(14,15 )(17, 18)(20,21) If the cheap option is given, the function only tries to reduce to orbits or� Given a collection of distinct integers, return all possible permutations. Example: #16 3Sum Closest #18 4Sum. Medium #19 Remove Nth Node From End of List

[PDF] Strategies for advanced applications of permutation–inversion , ations applied to only part of the molecule,” i.e., as rotations and reflections applied to script 4, etc. If several permutations are to be applied in succession, e.g.,. Knuth's The Art of Computer Programming, Volume 4, Fascicle 2: Generating all Tuples and Permutations gives efficient (non-recursive) solutions to this and many other combinatorial enumeration problems. Section 7.2.1.2 contains 36 pages of material devoted to precisely the question you ask.

Comments
  • I realize that my question could have been asked in a better way. I've made an update. @ChrisDoyle
  • please don't close this, i am working on a solution.
  • 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
  • Could you please comment ony why you think the question focus on more than one problem? @jonrsharpe
  • 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)]]
  • First print of this code yields (96, 66, 11, 91), (99, 18, 86, 61), (99, 18, 86, 61), {88, 89, 19, 68}), where (99, 18, 86, 61) is present twice, which is not valid. Since 99 only appears once in the list
  • small error on the yield there, yielded i,k,k instead of i,k,j
  • note: this will break horribly if you have duplicate keys
  • Hmm, the initial list that I provided keys = [18, 99, 86, 61, 66, 81, 98, 19, 91, 16, 69, 88, 89, 68, 11, 96] isnt listed in your print, yet it fufills the conditions
  • added how to get the complete list (it is long though)