permutation without repitition-CodePudding

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?

CodePudding user response：

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