8

In a program I am making that generates anagrams for a given set of letters, my current approach is to:

  1. Get all the the combinations of all the letters
  2. Get the permutations of each combination group
  3. Sort the resulting permutations alphabetically
  4. Remove duplicate entries

My question pertains to the mathematics of permutations. I am wondering if it is possible to flat-out calculate the array size needed to store all of the remaining entries after removal of duplicate entries (using, say, the number of repeated letters in conjunction with the permutation formula or something).

I apologize about the vagueness of my question, I am still researching more about combinations and permutations. I will try to elaborate my goal as my understanding of combinations and permutations expands, and once I re-familiarize myself with my program (it was a spare-time project of mine last summer).

Improve this question
1

2 Answers 2

Reset to default
1

If you have n elements, and a[0] duplicates of one element, a[1] duplicates of another element, and so on up to a[k], then the total number of distinct permutations (up to duplicates) is n!/(a[0]! a[1]! ... a[k]!).

FYI, if you're interested, with Guava you could write

Collection<List<Character>> uniquePermutations = Collections2.orderedPermutations(Lists.charactersOf(string));

and the result would be the unique permutations of the characters, accounting for duplicates and everything. You could even call its .size() method -- or just look at its implementation for hints. (Disclosure: I contribute to Guava.)

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

he didn't ask the number of duplicates, bu how to get them.
"I am wondering if it is possible to flat-out calculate the array size needed to store all of the remaining entries after removal of duplicate entries." That sounds like asking for the number of distinct permutations to me.
Sounds to me more like yes/no question :)
Yes, distinct permutations sounds like what I am looking for. I would appreciate it if you could elaborate on the general solution you gave, I'm afraid I don't fully understand. In particular, what is meant with a[number]. It looks like you mean the a[k] is the number of duplicates for a given combination group, is that correct?
0

Generating all the permutations is really bad idea.The word "overflow" for instance has 40320 permutations. So the memory consumption gets really high as your word length grows.

I believe that the problem you are trying to solve can be reduced to finding out if one word is an anagram of another.

Then you can solve it by counting how many times each letter occurs (it will be a 26-tuple) and comparing these tupples against each other.

Improve this answer

Comments