1

If I have a string (e.g. 'AABC'), how can I calculate the number of possible unique strings?

The answer is 12 in this case, but how can I caclulate this with an algorithm?

I could do it for 'ABC', but having the repeated character confuses me.

I'm trying to do it in Python

Edit: Also, I am not looking to generate all the possible strings, only to calculate the number.

bleurhgarator
  • 13
  • 3
  • Take a look at http://stackoverflow.com/questions/361/generate-list-of-all-possible-permutations-of-a-string – Celeo Nov 05 '14 at 23:26
  • I don't think those are applicable. I tried some and given 'AABC' it will generate multiple of the same string. – bleurhgarator Nov 06 '14 at 00:06

2 Answers2

2

You could walk through all the permutations and count the unique one using the itertools module

import itertools

string = "AABC"
count = len(set(itertools.permutations(string)))
print(count)

But since you just need the count, you can do that a bit more easily:

import math
import collections

string = "AABC"

chars = collections.Counter(string)
denominator = reduce(lambda x,y: x * math.factorial(y), chars.values(), 1)
count = math.factorial(len(string)) / denominator
print(count)
linus
  • 336
  • 1
  • 9
  • s/a bit more easily/more efficiently/ – gboffi Nov 05 '14 at 23:58
  • Wow, that is super impressive and seems correct, a bit of googling leads me to believe it has something to do with binomial coefficients, but the wikipedia article is way beyond me. In laymans terms, could you explain it? – bleurhgarator Nov 06 '14 at 00:28
  • Say you have n unique items (alphabets in this case), and you want to count the total number of ways you can arrange them. There are n ways to select the first item for an arrangement, then (n - 1) ways to select the second, then (n - 2) for the third and so on. So the total number of arrangements becomes n * (n - 1) * (n - 2) * ... * 1. Or in other words, n!. – linus Nov 06 '14 at 01:04
  • Now say some of those items are duplicates. In the OP's example, there are 2 As. Following the same logic as above, there are 2! ways to arrange these 2 As, but they will generate duplicate arrangements. So you'll end up with "AABC" and "AACB" repeated 2! times. Simply divide by 2! to get the unique arrangements. To generalize, if the n items contain n1 items of one type, n2 of another, etc. the number of unique arrangements is n!/(n1!*n2!...) – linus Nov 06 '14 at 01:04
  • Thanks linus, that is an excellent answer and explanation and if I could make StackOverflow dispense beer directly to you, I would, but you'll have to make do with an accepted answer! :-) – bleurhgarator Nov 06 '14 at 01:09
0

You can do that with itertools module.

Open up your python interpreter.

import itertools
for unique in itertools.permutations("AABC"):
    print "".join(unique)

Just change "AABC" with whatever you want.

heartofrevel
  • 181
  • 1
  • 3
  • 12
  • You haven't noticed the word ***unique*** in the question title. – gboffi Nov 05 '14 at 23:44
  • **Hint** what's the main property of a `set`? Its elements are ***unique***. How do you make a `set` from an iterable? `set(iterable)`. Is a `set` an iterable? Oh yes. – gboffi Nov 05 '14 at 23:54
  • Thanks, but for large strings, this is going to be extremely time consuming when all that is required is the count. linus nailed it above. – bleurhgarator Nov 06 '14 at 01:16
  • Hey thanks gbofi, I just noticed that the output strings are not unique. – heartofrevel Nov 06 '14 at 02:31
  • @bleurhgarator - yeah for large strings this will consume a lot of time and yeah linus really nailed it – heartofrevel Nov 06 '14 at 02:32