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
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.
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())