Generating permutations - Computer Technical Help

Two Plus Two Forums Other Topics Computer and Technical Help

Generating permutations

Post Reply Subscribe

...

01-08-2022 , 10:55 AM

Gabethebabe

Malware Jedi

Join Date: Oct 2007 Posts: 27,387

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

AAAAA (1)
AAAAB (5)
AAABB (10)
AAABC (20)
AABBC (30)
AABCD (60)
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

Quote

01-09-2022 , 12:58 PM

Aceium

Carpal \'Tunnel

Join Date: Jan 2007 Posts: 7,437

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.

Quote

01-11-2022 , 04:06 PM

jukofyork

Carpal \'Tunnel

Join Date: Sep 2004 Posts: 11,749

Quote:

Originally Posted by Gabethebabe

AAAAA (1)
AAAAB (5)
AAABB (10)
AAABC (20)
AABBC (30)
AABCD (60)
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

Quote

01-12-2022 , 01:45 PM

A missread issue

Carpal \'Tunnel

Join Date: Aug 2020 Posts: 6,389

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.

Quote

01-14-2022 , 05:36 PM

Gabethebabe

Malware Jedi

Join Date: Oct 2007 Posts: 27,387

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

Quote

Post Reply Subscribe

...