2

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?

Community
  • 1
  • 1
Jimjam
  • 21
  • 2

1 Answers1

0

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

Paul Terwilliger
  • 1,596
  • 1
  • 20
  • 45