Calculating duplicate permutations in Python

Question

Say I have this list : [1,1,2,2] I want to run through all the permutations of this. If I print the same permutation will be printed 4 times. For [1,1,1,3] the same one will be printed 6 times, For [1,1,1,3,3] 12.

In General : (a1)!(a2)!...(an)! Is there any function that does that in Python? If no, can you give me an algorithm that does in Python?

You included the algorithm in your question. Your formula defines an algorithm. — Bartosz Marcinkowski, Feb 06 '15 at 12:07
Okay I know mathematics but I don't really know how to imply this knowledge to python — michael kova, Feb 06 '15 at 12:09
have you tried searching Google for factorial in python? then multiplying results in python? i think it does not require top coder level python experience. — Kamyar Ghasemlou, Feb 06 '15 at 12:10
A basic "python permutation" search leads you here from where you can identify the duplicates: http://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list-in-python — runDOSrun, Feb 06 '15 at 12:12
Well I need to know the amount of duplicates of every item in the list without counting the same thing twice.. — michael kova, Feb 06 '15 at 12:13
runDOSrun - I want to find a number, not to generate permutations. — michael kova, Feb 06 '15 at 12:14
You don't need to find out the number of duplicates algorithmically, it's mathematically well-defined: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm — runDOSrun, Feb 06 '15 at 12:14
How do I know in python how many duplicates of each item I have ? — michael kova, Feb 06 '15 at 12:19
`len(mylist)-len(set(mylist))` or just loop manually if you want to track it for every single item — runDOSrun, Feb 06 '15 at 12:23

score 0 · Answer 1 · answered Feb 06 '15 at 12:25

Are you looking for something like the following?

import math

def repeats(nums):
    counts = dict()
    result = 1

    for n in nums:
        if n in counts:
            counts[n] += 1
        else:
            counts[n] = 1

    for n in counts.keys():
        result *= math.factorial(counts[n])

    return result

print repeats([1, 1, 2, 2])     # prints 4
print repeats([1, 1, 1, 3])     # prints 6
print repeats([1, 1, 1, 3, 3])  # prints 12

Calculating duplicate permutations in Python

1 Answers1