Algorithm of permutations without repetition?

Question

In the program I am doing that generates anagrams for a given set of letters, my current approach is this:

• Get all combinations of all letters
• Get permutations of each group of combinations
• Sort the resulting permutations in alphabetical order
• Delete duplicate entries

My question is about math permutations. I am wondering if it is possible to calculate the size of the array needed to store all the remaining entries after deleting the duplicate entries (using, say, the number of duplicate letters combined with the permutation formula or something else).

I apologize for the vagueness of my question, I am still more versed in combinations and permutations. I will try to formulate my goal, as my understanding of combinations and permutations expands, and as soon as I re-evaluate myself with the help of my program (this was my last project last summer).

Answer 1

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

FYI, if you are interested, Guava you can write

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

and the result will be unique character permutations that take into account duplicates and that's it. You can even call its .size() method - or just look at its implementation for tips. (Disclosure: I contribute to Guava.)

Answer 2

Generating all permutations is a really bad idea. For example, the word overflow has 40,320 permutations. Thus, memory consumption becomes very high as the word length grows.

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

Then you can solve it by calculating how many times each letter happens (it will be a 26-tuple) and comparing these combinations with each other.