# Generate Unique Permutation From String With Repeating Character (Python)

February 22, 2019

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 results

def _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
``````

## 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
``````