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

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
This work is licensed under a
Creative Commons Attribution-NonCommercial 4.0 International License.