CODEWITHSUNDEEP
pythoniteratorgeneratorcombinationspermutation
Baffled
Baffled

Reputation: 13

Generating permutations that meet multiple criteria in Python?

I am trying to generate a list of all possible permutations that meet various sub-criteria. I can't do a brute force approach because memory usage would be an issue. Ideally I'd use some combination of itertools and a generator to manage the number of generated permutations.

Objective

To generate permutations of 20 items, which are split into four sub-sets of 5 items.

Constraints

  1. Each item can be equal to 4, 5 or 6
  2. The sum of each permutation set in aggregate must total 100
  3. The sum of each sub-set must total between 20 and 30

Example

66655 / 44455 / 46465 / 56644 would be permissible as the sub-components sum between 20 and 30 (28 / 22 / 25 / 25) and the aggregate total is equal to 100.

Unfortunately I don't really know where to start! Any guidance would be much appreciated.

Upvotes: 1

Views: 213

Answers (1)

Alain T.
Alain T.

Reputation: 42143

That will produce hundreds of millions of valid solutions. Storing them in a list would require 3GB of memory but you could generate the solutions without storing them.

Here's how you could produce them (i'm only counting them in this example):

Create a mapping between subset totals (20,21,22,...30) and the permutations of numbers 4,5,6 that can produce them

from itertools import permutations,product,chain

subSums = dict()
for combo in combinations([4,5,6]*5,5):
    if sum(combo) not in range(20,31): continue
    subSums.setdefault(sum(combo),set()).add(combo)
            
print(sum(map(len,subSums.values()))) # 243
for subtotal,combos in sorted(subSums.items()):
    print(subtotal,len(combos),":",[*combos][:3],"..."*(len(combos)>3))

20 1 : [(4, 4, 4, 4, 4)] 
21 5 : [(4, 5, 4, 4, 4), (5, 4, 4, 4, 4), (4, 4, 5, 4, 4)] ...
22 15 : [(4, 5, 4, 5, 4), (4, 4, 4, 6, 4), (4, 4, 5, 5, 4)] ...
23 30 : [(4, 4, 5, 6, 4), (4, 4, 6, 5, 4), (6, 5, 4, 4, 4)] ...
24 45 : [(5, 4, 6, 4, 5), (5, 4, 4, 6, 5), (5, 5, 4, 4, 6)] ...
25 51 : [(6, 4, 5, 6, 4), (6, 4, 6, 5, 4), (6, 5, 5, 5, 4)] ...
26 45 : [(5, 5, 5, 5, 6), (5, 4, 5, 6, 6), (5, 4, 6, 5, 6)] ...
27 30 : [(6, 5, 6, 5, 5), (6, 5, 5, 6, 5), (6, 6, 5, 6, 4)] ...
28 15 : [(4, 6, 6, 6, 6), (5, 5, 6, 6, 6), (6, 6, 4, 6, 6)] ...
29 5 : [(5, 6, 6, 6, 6), (6, 6, 6, 6, 5), (6, 5, 6, 6, 6)] ...
30 1 : [(6, 6, 6, 6, 6)]

Generate permutations of 4 subtotals in 20,21,22,...30 that add up to 100

groupSums = set()
for combo in combinations([*range(20,31)]*4,4):
    if sum(combo) != 100: continue
    groupSums.add(combo)
    
print(len(groupSums)) # 891
for group in sorted(groupSums): print(group)

(20, 20, 30, 30)
(20, 21, 29, 30)
(20, 21, 30, 29)
(20, 22, 28, 30)
(20, 22, 29, 29)
(20, 22, 30, 28)
(20, 23, 27, 30)
(20, 23, 28, 29)
(20, 23, 29, 28)
(20, 23, 30, 27)
...

For each permutation of the 4 subtotals, combine the permutations of 4,5,6 that can produce each subtotal

solutions      = [] # not going to actually fill this
totalSolutions = 0
for g1,g2,g3,g4 in groupSums:
    groupSolutions  = len(subSums[g1])
    groupSolutions *= len(subSums[g2])
    groupSolutions *= len(subSums[g3])
    groupSolutions *= len(subSums[g4])
    totalSolutions += groupSolutions

    # actual solutions would be
    # for solution in product(subSums[g1],subSums[g2],subSums[g3],subSums[g4]):
    #     solutions.append([*chain.from_iterable(solution)])
    
print(totalSolutions) # 377,379,369 solutions

If you only need to generate solutions (and not store them in a list), you could make a generator function:

def genGroups():
    for g1,g2,g3,g4 in groupSums:
        yield from product(subSums[g1],subSums[g2],subSums[g3],subSums[g4])

for solution in genGroups(): 
    g1,g2,g3,g4 = map(sum,solution)
    print((g1,g2,g3,g4),":",*chain.from_iterable(solution))

(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 4 4 5 6 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 4 4 6 5 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 6 5 4 4 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 5 6 4 4 4
(20, 30, 27, 23) : 4 4 4 4 4 6 6 6 6 6 6 5 6 5 5 5 5 4 5 4
...
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 4 5 6
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 5 4 6
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 6 5 5 4
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 6 4 5
(29, 21, 26, 24) : 5 6 6 6 6 5 4 4 4 4 6 6 5 4 5 4 5 4 6 5
...
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 6 6 5 5
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 5 6 6 5
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 5 6 6 5 6
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 5 6 5 6 6
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 6 6 6 4
(22, 28, 22, 28) : 5 4 5 4 4 6 5 6 5 6 5 4 5 4 4 6 5 6 5 6

Generating all the solutions without storing them takes 27 seconds on my laptop.

sum(1 for _ in genGroups()) # 377379369 in 27.49 seconds

The generator can be used to fill a list (instead of the for loop above):

L = list(genGroups())

Upvotes: 2

Related Questions