Open Side Menu Go to the Top
Register
Generating permutations Generating permutations

01-08-2022 , 10:55 AM
Br0s

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
  1. AAAAA (1)
  2. AAAAB (5)
  3. AAABB (10)
  4. AAABC (20)
  5. AABBC (30)
  6. AABCD (60)
  7. ABCDE (120)

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?

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
01-09-2022 , 12:58 PM
Could you run Heaps on a list like AAABB, and throw out duplicate items?

You could do it with a map like this:

A -> A
B -> A
C -> A
D -> B
E -> B

ABCDE goes to BACDE, which both equate to AAABB when mapped to your problem of interest. You can log results you haven't seen before, and throw out results that you have seen before.

It's not the most elegant but it seems like it might be a valid place to start.
01-11-2022 , 04:06 PM
Quote:
Originally Posted by Gabethebabe Generating permutations
Br0s

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
  1. AAAAA (1)
  2. AAAAB (5)
  3. AAABB (10)
  4. AAABC (20)
  5. AABBC (30)
  6. AABCD (60)
  7. ABCDE (120)

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).

Quote:
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:

[[1, 2, 3, 4, 5], [2, 1, 3, 4, 5], [[3, 2, 1, 4, 5], ...]

and then use these when you need them.

Depending on the inputs you might also need to sort your 5 elements (using a hard-coded sorting network) and then have an if statement to decide on the correct lookup table.

Juk

PS: If I've not understood you correctly then maybe add a few more details of what you want and I can likely help then too
01-12-2022 , 01:45 PM
Here's a quick solution in Python I just wrote:

Code:
def necklace(list,am):
    templist = []
    added = False
    for i in range(len(list)):
        if(am[i] > 0):
            am2 = am.copy()
            am2[i] -= 1
            added = True
            templist = templist + concatByPrefix(necklace(list,am2),list[i])
    if(not added):
        return [""]
    return templist

def concatByPrefix(list,pref):
    for i in range(len(list)):
        list[i] = pref+list[i]
    return list
And an example call using your case 4:

Code:
print(necklace(["a","b","c"],[3,1,1]))
Which outputs:

Quote:
['aaabc', 'aaacb', 'aabac', 'aabca', 'aacab', 'aacba', 'abaac', 'abaca', 'abcaa', 'acaab', 'acaba', 'acbaa', 'baaac', 'baaca', 'bacaa', 'bcaaa', 'caaab', 'caaba', 'cabaa', 'cbaaa']
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.
01-14-2022 , 05:36 PM
Thanks a lot

I had had the same idea as Yuk to just hardcode some lookup tables

That means not looping too much, no if statements

I can try the routine of AMI as well and check out which metod goes faster.

I have the project shelved for now, started a new job this week and it drains

      
m