I need efficient algorithms for generating all permutations of a list of 5 items, where duplicates are possible.
Heaps algorithm helps me only to generate all 120 permutations of a list of 5 different items. However, I want only a list of 5 results if the list is AAAAB or 30 results if the list is AABBC
These are the 7 scenarios I need to solve efficiently. 1 and 2 are easy. 7 I can use Heaps. How to generate all permutations of scenario 3-6?
The simplest method I can think of is to just generate all 5! permutations, sort them and save only the first occurrence.
There is probably a faster way to do this but if all you care about is sets of 5 items and you've identified all the possible ways they can repeat it doesn't really matter what method you use (see below).
I am programming in visual basic and it needs to be efficient, because it will have to run millions of times and it needs to finish before I die
Once you've generated each of the above you probably want to create lookup tables of indexes, eg:
The idea is to solve it recursively keeping track of available letters. The concatByPrefix is just a helper algorithm that adds a given letter "pref" to the start of every word in the given list. The necklace iterates over all the letters in the list, if a letter is available it reduces its availability by one and adds it to the beginning of the list it gets with a recursive call of the same algorithm.