CODEWITHSUNDEEP
pythonalgorithmpermutationcombinatoricsmore-itertools
Jimjam
Jimjam

Reputation: 41

Permutations of 2 characters in Python into fixed length string with equal numbers of each character

I've looked through the 2 questions below, which seem closest to what I am asking, but don't get me to the answer to my question.

Permutation of x length of 2 characters

How to generate all permutations of a list in Python

I am trying to find a way to take 2 characters, say 'A' and 'B', and find all unique permutations of those characters into a 40 character string. Additionally - I need each character to be represented 20 times in the string. So all resulting strings each have 20 'A's and 20 'B's.

Like this:

'AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB'
'AAAAAAAAAAAAAAAAAAABABBBBBBBBBBBBBBBBBBB'
'AAAAAAAAAAAAAAAAAABAABBBBBBBBBBBBBBBBBBB'

etc...

All I really need is the count of unique combinations that follow these rules. 

y=['A','A','A','A','B','B','B','B']
comb = set(itertools.permutations(y))
print("Combinations Found: {:,}".format(len(comb)))

This works, but it doesn't scale well to an input string of 20 'A's and 20 'B's. The above code takes 90 seconds to execute. Even just scaling up to 10 'A's and 10 'B's ran for 20 minutes before I killed it.

Is there more efficient way to approach this given the parameters I've described?

Upvotes: 4

Views: 936

Answers (3)

Raymond Hettinger
Raymond Hettinger

Reputation: 226624

The multinomial theorem lets you directly calculate the number of distinct arrangements. Here's an implementation in Python:

from math import comb, prod
from itertools import accumulate
from collections import Counter

def num_distinct_permutations(data):
    "Equivalent to: len(set(permuations(data)))"
    counts = list(Counter(data).values())
    return prod(map(comb, accumulate(counts), counts))

Use it like this:

>>> num_distinct_permutations('AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB')
137846528820

>>> num_distinct_permutations('toffee')
180

>>> from itertools import permutations
>>> len(set(permutations('toffee')))
180

Also of interest is the distinct_permutations function in the more_itertools project:

>>> from more_itertools import distinct_permutations, ilen

>>> ilen(distinct_permutations('toffee'))
180

>>> for p in distinct_permutations('toffee'):
...     print(p)
...
('e', 'e', 'f', 'f', 'o', 't')
('e', 'e', 'f', 'f', 't', 'o')
('e', 'e', 'f', 'o', 'f', 't')
('e', 'e', 'f', 'o', 't', 'f')
('e', 'e', 'f', 't', 'f', 'o')
('e', 'e', 'f', 't', 'o', 'f')
('e', 'e', 'o', 'f', 'f', 't')
 . . .

Upvotes: 2

Xavier Adaickalam
Xavier Adaickalam

Reputation: 56

import itertools
import string

def print_string():
    st = string.ascii_uppercase
    #st1 = itertools.permutations(st,2)
    st1 = itertools.product(list(st),repeat=2)
    count = 0
    for s1 in list(st1):
        print(''.join(s1))
        count = count +1
    print(count)

if __name__ == '__main__':
    print_string()

Upvotes: 0

Paul Terwilliger
Paul Terwilliger

Reputation: 1656

If all you need is the count, this can be generalized to n choose k. Your total size is n and the number of elements of "A" is k. So, your answer would be:

(n choose k) = (40 choose 20) = 137846528820

Upvotes: 1

Related Questions