Generate Unique Permutation From String With Repeating Character (Python)

Generate permutations of a string with repetitive character (e.g. aabc). The permutations must not contain duplicates (unique).

aa = aa
aab = aab, aba, baa
aabc = aabc, aacb, abac, abca, ...

Solution 1

You can use standard permutation solution, but it will contain repetition.

standard_permutation('aab') = ['aab', 'aba', 'aab', 'aba', 'baa', 'baa']

You can use a hashtable (store unique results) to eliminate duplication.

Solution 2

What if we want to create unique permutation only?

First we need to need the count of each character.

aaabbc = 3a, 2b, 1c

Imagine the following

P( 3a | 2b | 1c ) = a + P( 2a | 2b | 1c ) +
                    b + P( 3a | 1b | 1c ) +
                    c + P( 3a | 2b | 0c )


P( 2a | 2b | 1c ) = a + P( 1a | 2b | 1c ) +
                    b + P( 2a | 1b | 1c ) +
                    c + P( 2a | 2b | 1c )

P( 3a | 1b | 1c ) = ...

P( 3a | 2b | 0c ) = ...

We start with each character (a, b, c), but find permutation of the remaining character, and append character to a prefix.

def permutations(text):    results = []    count_map = _build_frequency_count(text)    _permutations(count_map, "", len(text), results)    return resultsdef _permutations(count_map, prefix, remaining, results):    # base    if remaining == 0:        results.append(prefix)        return    # try remaining character    for c in count_map.keys(): # [a, b, c], loop once for each char only        count = count_map[c]        if count > 0:            # reduce character: e.g. P(2a) -> P(1a)            count_map[c] -= 1            _permutations(count_map, prefix+c, remaining-1, results)            # restore for next character iteration: b            count_map[c] = count def _build_frequency_count(text):    count_map = {}    for c in text:        if c not in count_map:            count_map[c] = 0        count_map[c] += 1    return count_map

Solution 3

Validate Result

To validate the result, the mathematical formula to calculate number of permutation with repetition is n! / (a!b!c!) (a = count of character a).

aa = 2a = 2! / 2! = 1
aab = 2a1b = 3! / (2!*1!) = 3*2*1 / (2*1*1) = 6 / 2 = 3
aaabbc = 3a2b1c = 6! / (3!*2!*1!) = 720 / (6*2*1) = 720 / 12 = 60