4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Hadn't considered using Counter, it looks better :) \$\endgroup\$ – James Schinner Mar 20 '18 at 21:25
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Eric Duminil Mar 20 '18 at 15:16
  • \$\begingroup\$ Thanks for the Terminology. @EricDuminil at least all imports are from the standard library. \$\endgroup\$ – James Schinner Mar 20 '18 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.