N = 14 SIZE = 6 lst = range(N+1) sum_n_combs = [ list(comb) for comb in it.combinations_with_replacement(lst, SIZE) if sum(comb) == N ] print(sum_n_combs) output [[0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 1, 13], [0, 0, 0, 0, 2, 12], [0, 0, 0, 0, 3, 11], [0, 0, 0, 0, 4, 10], [0, 0, 0, 0, 5, 9], [0, 0, 0, 0, 6, 8], [0, 0, 0, 0, 7, 7], [0, 0, 0, 1, 1, 12], [0, 0, 0, 1, 2, 11], [0, 0, 0, 1, 3, 10], [0, 0, 0, 1, 4, 9], [0, 0, 0, 1, 5, 8], [0, 0, 0, 1, 6, 7], [0, 0, 0, 2, 2, 10], [0, 0, 0, 2, 3, 9], [0, 0, 0, 2, 4, 8], [0, 0, 0, 2, 5, 7], [0, 0, 0, 2, 6, 6], [0, 0, 0, 3, 3, 8], [0, 0, 0, 3, 4, 7], [0, 0, 0, 3, 5, 6], [0, 0, 0, 4, 4, 6], [0, 0, 0, 4, 5, 5], [0, 0, 1, 1, 1, 11], [0, 0, 1, 1, 2, 10], [0, 0, 1, 1, 3, 9], [0, 0, 1, 1, 4, 8], [0, 0, 1, 1, 5, 7], [0, 0, 1, 1, 6, 6], [0, 0, 1, 2, 2, 9], [0, 0, 1, 2, 3, 8], [0, 0, 1, 2, 4, 7], [0, 0, 1, 2, 5, 6], [0, 0, 1, 3, 3, 7], [0, 0, 1, 3, 4, 6], [0, 0, 1, 3, 5, 5], [0, 0, 1, 4, 4, 5], [0, 0, 2, 2, 2, 8], [0, 0, 2, 2, 3, 7], [0, 0, 2, 2, 4, 6], [0, 0, 2, 2, 5, 5], [0, 0, 2, 3, 3, 6], [0, 0, 2, 3, 4, 5], [0, 0, 2, 4, 4, 4], [0, 0, 3, 3, 3, 5], [0, 0, 3, 3, 4, 4], [0, 1, 1, 1, 1, 10], [0, 1, 1, 1, 2, 9], [0, 1, 1, 1, 3, 8], [0, 1, 1, 1, 4, 7], [0, 1, 1, 1, 5, 6], [0, 1, 1, 2, 2, 8], [0, 1, 1, 2, 3, 7], [0, 1, 1, 2, 4, 6], [0, 1, 1, 2, 5, 5], [0, 1, 1, 3, 3, 6], [0, 1, 1, 3, 4, 5], [0, 1, 1, 4, 4, 4], [0, 1, 2, 2, 2, 7], [0, 1, 2, 2, 3, 6], [0, 1, 2, 2, 4, 5], [0, 1, 2, 3, 3, 5], [0, 1, 2, 3, 4, 4], [0, 1, 3, 3, 3, 4], [0, 2, 2, 2, 2, 6], [0, 2, 2, 2, 3, 5], [0, 2, 2, 2, 4, 4], [0, 2, 2, 3, 3, 4], [0, 2, 3, 3, 3, 3], [1, 1, 1, 1, 1, 9], [1, 1, 1, 1, 2, 8], [1, 1, 1, 1, 3, 7], [1, 1, 1, 1, 4, 6], [1, 1, 1, 1, 5, 5], [1, 1, 1, 2, 2, 7], [1, 1, 1, 2, 3, 6], [1, 1, 1, 2, 4, 5], [1, 1, 1, 3, 3, 5], [1, 1, 1, 3, 4, 4], [1, 1, 2, 2, 2, 6], [1, 1, 2, 2, 3, 5], [1, 1, 2, 2, 4, 4], [1, 1, 2, 3, 3, 4], [1, 1, 3, 3, 3, 3], [1, 2, 2, 2, 2, 5], [1, 2, 2, 2, 3, 4], [1, 2, 2, 3, 3, 3], [2, 2, 2, 2, 2, 4], [2, 2, 2, 2, 3, 3]]
As “combinations with replacement” does, this function only produces the combination. I want permutation of each combination without repetition. For example
[[0, 0, 0, 0, 0, 14], [0, 0, 0, 0, 14, 0] ... [3, 2, 3, 2, 2, 2], [3, 3, 2, 2, 2]]
When I tried to do this by
ret=[] for i in range(90): ret.extend(it.permutations(sum_n_combs[i], SIZE))
Time complexity was exponential, and made repititions When I tested with one list sum_n_combs[0], which is [0, 0, 0, 0, 0, 14] produced 720 permutations when I only want 6 of them(14 at each different place).
How can I make permutation without repetition for each combination in an efficient way?
Advertisement
Answer
You could separate this in two steps:
- generate partitions of the targeted sum
- generate distinct permutations of each partition
Recursive generators will allow you to get the results efficiently without trial/error filtering and without storing everything in memory:
def partitions(N,size): if size == 1 : yield (N,) # base case, only 1 part return for a in range(N//size+1): # smaller part followed by for p in partitions(N-a*size,size-1): # equal or larger ones yield (a, *(n+a for n in p)) # recursing on delta only def permuteDistinct(A): if len(A) == 1: yield tuple(A) # single value return used = set() # track starting value for i,n in enumerate(A): # for each starting value if n in used: continue # not yet used used.add(n) for p in permuteDistinct(A[:i]+A[i+1:]): yield (n,*p) # starting value & rest
output:
N = 14 SIZE = 6
PARTITIONS…
for part in partitions(N,SIZE): print(part) (0, 0, 0, 0, 0, 14) (0, 0, 0, 0, 1, 13) (0, 0, 0, 0, 2, 12) (0, 0, 0, 0, 3, 11) (0, 0, 0, 0, 4, 10) (0, 0, 0, 0, 5, 9) (0, 0, 0, 0, 6, 8) (0, 0, 0, 0, 7, 7) (0, 0, 0, 1, 1, 12) (0, 0, 0, 1, 2, 11) (0, 0, 0, 1, 3, 10) (0, 0, 0, 1, 4, 9) (0, 0, 0, 1, 5, 8) (0, 0, 0, 1, 6, 7) (0, 0, 0, 2, 2, 10) (0, 0, 0, 2, 3, 9) (0, 0, 0, 2, 4, 8) (0, 0, 0, 2, 5, 7) (0, 0, 0, 2, 6, 6) (0, 0, 0, 3, 3, 8) (0, 0, 0, 3, 4, 7) (0, 0, 0, 3, 5, 6) (0, 0, 0, 4, 4, 6) (0, 0, 0, 4, 5, 5) ...
PERMUTED PARTITIONS (DISTINCT):
for part in partitions(N,SIZE): for permutedPart in permuteDistinct(part): print(permutedPart) (0, 0, 0, 0, 0, 14) (0, 0, 0, 0, 14, 0) (0, 0, 0, 14, 0, 0) (0, 0, 14, 0, 0, 0) (0, 14, 0, 0, 0, 0) (14, 0, 0, 0, 0, 0) (0, 0, 0, 0, 1, 13) (0, 0, 0, 0, 13, 1) (0, 0, 0, 1, 0, 13) (0, 0, 0, 1, 13, 0) (0, 0, 0, 13, 0, 1) (0, 0, 0, 13, 1, 0) (0, 0, 1, 0, 0, 13) (0, 0, 1, 0, 13, 0) (0, 0, 1, 13, 0, 0) (0, 0, 13, 0, 0, 1) (0, 0, 13, 0, 1, 0) (0, 0, 13, 1, 0, 0) ...