Python calculate arrangements of sequence

Question

I have just started thinking about probabilities. A Problem that come up was how to calculate all the potential arrangements for a given sequence. By arrangement I mean unique permutation.

I initially used this method:

from itertools import permutations
sequence = '11223344'
len(set(permutations(sequence)))
# 2520

But for long sequences this can take a long time! (or run out of memory)

I came up with this function arrangements

from math import factorial
from functools import reduce
from operator import mul
def arrangements(sequence):
 return factorial(len(sequence))/reduce(mul,
 [factorial(sequence.count(i)) for i in set(sequence)])
# arrangements(sequence)
# 2520.0

My thinking is this:

For a given length sequence with all unique items there are factorial(len(sequence)) permutations.

For every repeated item in the sequence there will be factorial(#repeats) that will result in the same permutation.

My function calculates all permutations / all repeated permutations.

I'm sure I have reinvented an already existing standard python function somewhere. I'd like to know if my thinking is sound and the implementation makes sense.

Wouldn't itertools.arrangements be cool?

Answer 1

Notes

• I'd expect arrangements to return the unique permutations of sequence, not just how many there are.
• If it returns a number, it should be an integer.
• You could use collections.Counter instead of counting the integers again and again.
• You're right, it would be nice to have itertools.unique_permutations. In the meantime, I often come back to this SO answer.

Possible refactoring

from math import factorial
from functools import reduce
from collections import Counter
from operator import mul
def count_unique_permutations(sequence):
 count_permutations = factorial(len(sequence))
 repetitions = (factorial(v) for v in Counter(sequence).values())
 return count_permutations // reduce(mul, repetitions)

• James Schinner: Hadn't considered using Counter, it looks better :)

Answer 2

The keyword to search for is "multinomial coefficient". That returns this answer: https://stackoverflow.com/questions/46374185/does-python-have-a-function-which-computes-multinomial-coefficients

• Eric Duminil: Good to know. The linked code isn't very readable IMHO but it has the merit of not needing 4 imports for 4 lines of code.
• James Schinner: Thanks for the Terminology. @EricDuminil at least all imports are from the standard library.