Equivalents permutations function

Question

My function is supposed to essentially give the cartesian product of all the letters in a string with the caveat that you have to give the permutations of every equivalent of each character in a string (capital and lowercase for example). This is what I came up with but I believe it has a time complexity of \$O(n*k^n)\$, \$k\$ being the number of equivalents of each character.

import string
from pprint import pprint

equivs = {x[0]:x for x in list(zip(string.ascii_lowercase,string.ascii_uppercase))}

st = "missifsffs"


def perms(st):
    st = st.lower()
    out = [""]
    for let in st:
        out = [y+x for y in out for x in equivs[let]]
    return out
print(perms("miss")) #['miss', 'misS', 'miSs', 'miSS', 'mIss', 'mIsS', 'mISs', 'mISS', 'Miss', 'MisS', 'MiSs', 'MiSS', 'MIss', 'MIsS', 'MISs', 'MISS']
print(perms("okay")) #['okay', 'okaY', 'okAy', 'okAY', 'oKay', 'oKaY', 'oKAy', 'oKAY', 'Okay', 'OkaY', 'OkAy', 'OkAY', 'OKay', 'OKaY', 'OKAy', 'OKAY']



print(perms(st))

Answer 1

For starter, you shouldn't use abreviations for your variables/functions names: perms for permutations, st for string, let for letter, equiv for equivalence_table… You gain nothing doing so, except obfuscating what is going on which impairs readability.

Then I find that your function has a wrong name, as permutations refers more naturally to swapping the order of the letters. I would rather use something along the line of case_swap or character_equivalence. I find these names more descriptive in constructs of the form for word in <function_name>('I got it.').

Now, what about the behaviour of your function when given a string with characters that are not in string.ascii_lowercase or string.ascii_uppercase, as the spaces or the dot in my previous example? You should handle such cases where let is not a key in equivs. And the simplest to do so is to fallback to using only let in such cases: equivs[let] can become equivs.get(let, let).

An other thing, that I particularly like with Python, is how it is simple to write lazy functions. Instead of building whole lists of results and storing them in memory, you can just yield intermediate results as you compute them. And I have the feeling that such function would benefit from being writen as a generator since I believe it will most likely be called to iterate over its result. And to do that without computing a whole bunch of intermediary string before the first usefull result, we can:

• use a recursive function to prepend the equivalents of the first letter to the computed equivalents of the rest of the string; or
• ask python to generate the cartesian product by providing ourselves a list of equivalent values for each letter.

The recursive function would look like:

def swap_case(sentence, equivalence_table):
    letter, *rest = sentence
    equivalents = equivalence_table.get(letter, letter)
    if not rest:
        yield from equivalents
    else:
        for end in swap_case(rest, equivalence_table):
            for symbol in equivalents:
                yield symbol + end

but recursion has its limits, especially in the number of function calls you can perform. So I would prefer to use the product generator from itertools to leverage fast iteration optimized in C:

import itertools


def swap_case(sentence, equivalence_table):
    equivalent_letters = (equivalence_table.get(l, l) for l in sentence)
    for characters in itertools.product(*equivalent_letters):
        yield ''.join(characters)

Here the join is needed since itertools.product generates lists of values taken from the provided iterables.

You can also sacrifice a bit of readability to continue iterating in C rather than using a for loop in Python by using map to apply ''.join to each list yielded by itertools.product:

def swap_case(sentence, equivalence_table):
    equivalent_letters = (equivalence_table.get(l, l) for l in sentence)
    return map(''.join, itertools.product(*equivalent_letters))

All in all, both version doesn't change the time complexity of the algorithm since you still have to generate the same amount of values. But the memory usage should be drastically lower.

---

You may also have noted that I changed the signature to include the equivalence table as a parameter. This is twofold:

1. easier testing as the function does not relly on a global variable;
2. parametrizable output as we may want some equivalences in some cases but not in others.

And if we want to easily provide various equivalence tables, we should as well write a function that makes it for us. Looking back at how swap_case will handle it, we should provide the equivalent letters as a value for each of the symbols as a key. Let's also provide an option to include/exclude uppercase letter as well:

def build_equivalence_table(use_uppercase=True, **kwargs):
    values = string.ascii_lowercase
    if use_uppercase:
        values = map(''.join, zip(values, string.ascii_uppercase))
    table = dict(zip(string.ascii_lowercase, values))
    for letter, equivalents in kwargs.items():
        table[letter.lower()] += equivalents
    # At this points, keys of `table` are only lowercase letters
    # let's include all the variants as well
    return {variant: group for group in table.values() for variant in group}

Usage being:

>>> build_equivalence_table(a='@4', t='7', l='!1', e='3')
{'p': 'pP', 'k': 'kK', 'r': 'rR', 'V': 'vV', 'U': 'uU', 'I': 'iI', 'i': 'iI', 'J': 'jJ', 'A': 'aA@4', 'n': 'nN', 's': 'sS', 'K': 'kK', 'D': 'dD', '1': 'lL!1', 'j': 'jJ', 'z': 'zZ', 'B': 'bB', 'w': 'wW', 'C': 'cC', 'P': 'pP', 'N': 'nN', 'Y': 'yY', 'G': 'gG', 'g': 'gG', 'q': 'qQ', 'T': 'tT7', 'h': 'hH', 'M': 'mM', '7': 'tT7', '!': 'lL!1', 'F': 'fF', 'd': 'dD', 'X': 'xX', 'l': 'lL!1', 'f': 'fF', 't': 'tT7', 'y': 'yY', 'e': 'eE3', 'x': 'xX', 'v': 'vV', 'b': 'bB', 'H': 'hH', 'Z': 'zZ', 'L': 'lL!1', 'S': 'sS', 'c': 'cC', 'a': 'aA@4', 'Q': 'qQ', '4': 'aA@4', 'W': 'wW', 'E': 'eE3', 'R': 'rR', 'o': 'oO', '@': 'aA@4', 'm': 'mM', '3': 'eE3', 'u': 'uU', 'O': 'oO'}

Answer 2

To add a few things to Mathias' excellent answer...

First let's clean it up a bit. We'll put the testing code inside a main() function, as the entry point of the program:

def main():
    # Testing permutations
    print(perms("miss"))
    print(perms("okay"))
    print(perms("missifsffs"))

Then we can run main() if this script is ran as entry point/stand alone, but not run it if it is imported into another script. See this Stack Overflow answer for details about how this works.

if __name__ == "__main__":
    main()

We can rename some things to make them more clear, as well as add Python 3's type hints in the permutation function:

letter_equivalents_map = {x[0]:x for x in list(zip(
        string.ascii_lowercase, 
        string.ascii_uppercase))}

def permutate_lower_upper(input_str: str) -> list:
    input_str = input_str.lower()
    out = [""]
    for letter in input_str:
        out = [y+x for y in out for x in letter_equivalents_map[letter]]
    return out

After running it I noticed a problem, that is, if the input string the function is called with is not strictly made of letters, the program crashes with an error:

print(permutate_lower_upper("hello,world")) 
# KeyError: ','

The simplest fix would be to handle the error if it happens with try...except:

def permutate_lower_upper(input_str: str) -> list:
    input_str = input_str.lower()
    out = [""]
    try:
        for letter in input_str:
            out = [y+x for y in out for x in letter_equivalents_map[letter]]
    except KeyError:
        out = [""]
        print("String containts invalid, non-letter characters")
    return out

Then if we call the function with the same string, we get this:

print(permutate_lower_upper("hello,world"))
# String containts invalid, non-letter characters
# ['']

You could think of other ways to handle those as well, such as expand the list of supported characters, all depending on the scope of your function.