strobogrommatic.py

def combinations(half, options):
    res = [""]
    for i in range(half):
        new_result = []
        for s in res:
            for o in options:
                new_result.append(o+s)
        res = new_result
    return res

def strobogrammatic_number(i):
    if i == '6':
        return '9'
    if i == '9':
        return '6'
    return i

def reverse_half(half):
    res = ""
    for c in reversed(half):
        res += strobogrammatic_number(c)
    return res

def strobogrammatic(n):
    half_length = int(n/2)
    all_combinations = combinations(half_length, ['0', '1', '6', '8', '9'])

    res = []
    if n % 2 == 0:
        for combination in all_combinations:
            res.append(combination + reverse_half(combination))
    else:
        for combination in all_combinations:
            for c in ['0', '1', '8']:
                res.append(combination + c + reverse_half(combination))
    return res

print(reverse_half("66"))
print(strobogrammatic(3))
print(strobogrammatic(4))