The problem

I happen to come accross this programming problem, which I find a bit challenging.

Tom is playing his favorite adventure game and got stuck in a puzzle. This puzzle requires him to press a​ sequence of buttons to unlock a door. However, the game does not tell Tom the button sequence directly but via a encoded string.

Tom knows that one unique character​ of the encoded string must correspond to ​one button​. However, he has no further clues on the mapping, i.e. which character in the string is which button. As a result, Tom has to try all the possible mappings to find the correct button sequence.

For example:

The sequence is AABBABAB, and there are 3 buttons, labelled 1, 2, 3

There are 2 uniques characters: A, and B. There are 3 buttons 1, 2, and 3. So, there are only 6 possible mappings:

• 11221212 # A = 1, B = 2
• 11331313 # A = 1, B = 3
• 22112121 # A = 2, B = 1
• 22332323 # A = 2, B = 3
• 33113131 # A = 3, B = 1
• 33223232 # A = 3, B = 2

At first, I thought “Ok, this is easy. I have to try all the cases. This is just brute-forcing, so I just need a few for loops”, but then I realized it wasn’t that simple.

The number of possible mappings is the k-permutation of the buttons, in which k is the number of unique characters in the sequence.

While it’s totally possible to implement the permutation algorithm without recursion, I find the recursion algorithm much easier to understand.

Algorithm

The problem was an example of a interview question for senior software engineer, in which the candidate is required to write the test in C/C++. However, I long have forsaken C/C++, thus I am going to write the algorithm this in Python.

Personally, I find Python much more friendly to algorithm learning than C/C++.

Partial permutation (k-permutation)

Applying a function to all arrrangements of k distinct elements selected from a list

def _partial_permute(prefix, suffix, k, func):
    if len(prefix) == k:
        func(prefix)
    else:
        for i, c in enumerate(suffix):
            _prefix = prefix + [c]
            _suffix = suffix[:i] + suffix[i + 1:]
            _partial_permute(_prefix, _suffix, k, func)

def _partial_permute(sequence, k, func):
    _partial_permute([], sequence, k, func)

Example usage

def func(permutation):
    print "".join(permutation)

partial_permute(list("ABCDE"), 3, func)

Full permutation

Applying a function to all permutions of elements in a list

def _permute(prefix, suffix, func):
    if not suffix:
        func(prefix)
    else:
        for i in xrange(len(suffix)):
            _prefix = prefix + [suffix[i]]
            _suffix = suffix[:i] + suffix[i + 1:]
            _permute(_prefix, _suffix, func)

def permute(sequence, func):
    _permute([], sequence, func)

Notes: The full permutation can as well be written as the k-permutation of the list, in which k is the length of the list.

def permute(sequence, func):
    partial_permute(sequence, len(sequence), func)

Example usage

def func(permutation):
    print "".join(permutation)

permute(list("ABCDE"), func)

The solution

def _partial_permute(prefix, suffix, k, func):
    if len(prefix) == k:
        func(prefix)
    else:
        for i, c in enumerate(suffix):
            _prefix = prefix + [c]
            _suffix = suffix[:i] + suffix[i + 1:]
            _partial_permute(_prefix, _suffix, k, func)

def partial_permute(sequence, k, func):
    _partial_permute([], sequence, k, func)

def print_possible_mapping(sequence, n):
    sequence = list(sequence)
    uniques = list(set(sequence))

    if n < len(uniques):
        print "There are more buttons than the number of unique characters in the sequence"
        return

    buttons = range(1, n + 1)

    def func(buttons_permutation):
        charmap = {}
        for i, c in enumerate(uniques):
            charmap[c] = buttons_permutation[i]
        _sequence = "".join([str(charmap[c]) for c in sequence])
        print _sequence

    partial_permute(buttons, len(uniques), func)

# Test
print "------ Test 1 ------"
print_possible_mapping("AABBABAB", 2)
print "------ Test 2 ------"
print_possible_mapping("AABBABAB", 3)
print "------ Test 3 ------"
print_possible_mapping("EFEBBBFF", 3)