CODEWITHSUNDEEP
pythonpython-itertools
MDP89
MDP89

Reputation: 336

Number of permutation with repetition in Python?

Is there a function to calculate the number of permutations with repetition in Python? I know with itertools I can generate them but I want only a faster way to do the calculation and avoid calculating the factorials, I'm not interested in generating all possible permutations.

Example: calculate the possible strings composed by 4 As, 3 Bs, 5 Cs.

result = 12!/(4!3!5!)

Or in code:

from math import factorial
from functools import reduce
rep = [4,3,5]
result = factorial(sum(rep)) // reduce(lambda x,y: x*y, map(factorial, rep))

"What kind of inputs is this approach too slow for?" The case that made me look into this topic was rep=[15000000,2], very big number with extreme difference: the simplified version would be a easy multiplication 15000000*14999999/2.

Upvotes: 6

Views: 634

Answers (1)

Stefan Pochmann
Stefan Pochmann

Reputation: 28656

Example: calculate the possible strings composed by 4 As, 3 Bs, 5 Cs.

result = 12!/(4!3!5!)

You can instead compute that by first choosing 4 out of the 12 spots for the As, then choosing 3 out of the remaining 8 spots for the Bs, and finally choosing 5 out of the remaining 5 spots for the Cs (the final step is optional, costs time but simplifies formula and code).

So:

result = (12 choose 4) * (8 choose 3) * (5 choose 5)

Or starting empty and building it up:

result = (4 choose 4) * (7 choose 3) * (12 choose 5)

The latter in Python:

from math import prod, comb
from itertools import accumulate
rep = [4,3,5]
result = prod(map(comb, accumulate(rep), rep))

Solves your example rep=[15000000,2] in an instant.

Attempt This Online!

Upvotes: 1

Related Questions