Does my permutation function demonstrate a good use of recursion?

Question

Once again, I am going through another MIT OpenCourseWare problem set for their introductory Python class. I am very weak when it comes to using recursion to solve problems. I was hoping to get some feedback about whether I have effectively used recursion for the following problem.

Here is my main function get_permutations:

def get_permutations(sequence):
    '''
    Parameters
    ----------
    sequence : str
        A string of letters without spaces

    Returns
    -------
    _list
        A list of all possible permutations of the string 'sequence'

    '''
    if len(sequence)==1:
        return sequence
    if len(sequence)==2:
        rev_seq=sequence[::-1]
        return [sequence,rev_seq]
    if len(sequence)==3:
        lhs=get_permutations(sequence[:-1])
        for count,_var in enumerate(lhs):
            lhs[count]=lhs[count]+sequence[-1]
        rhs=get_permutations(sequence[1:])
        for count,_var in enumerate(rhs):
            rhs[count]=rhs[count]+sequence[0]
        ends=get_permutations(sequence[::(len(sequence)-1)])
        for count,_var in enumerate(ends):
            ends[count]=ends[count]+sequence[1]
        sequence=lhs
        sequence.extend(rhs)
        sequence.extend(ends)
        return sequence
    _sequence=get_permutations(sequence[:-1])
    _list=[]
    for _var in _sequence:
        _list.extend((ins_chr_thru_str(_var,get_permutations(sequence[len(_sequence[0])]))))
    return _list

Here is the helper function ins_chr_thru_str

def ins_chr_thru_str(string,char):
    '''
    Parameters
    ----------
    string : str
        The parent string which will have the character inserted into it
        at various positions
    char : string
        A single character that will be inserted into the string

    Returns
    -------
    chr_ins_list : list
        A list of the strings with the char inserted throughout

    '''
    chr_ins_list=[]
    for x in range(len(string)+1):
        chr_ins_list.append(string[:x]+char+string[x:])
    return chr_ins_list

As an example, executing the command get_permutations("abcd") yields:

['dabc', 'adbc', 'abdc', 'abcd', 'dbac', 'bdac', 'badc', 'bacd', 'dbca', 'bdca', 'bcda', 'bcad', 'dcba', 'cdba', 'cbda', 'cbad', 'dacb', 'adcb', 'acdb', 'acbd', 'dcab', 'cdab', 'cadb', 'cabd']

Did I use the appropriate number of base calls? Is there any other way to use less base calls to yield the same result? Or is there another way you all could suggest to simplify this code?

Check this out: https://stackoverflow.com/a/13109403/1305461 — felipe, May 05 '20 at 23:22
@Felipe Thank you for the link! I'll look through their method which is much more concise than mine. — anonykit, May 05 '20 at 23:42

score 1 · Answer 1 · answered May 17 '20 at 03:48

Hey I'm also going through the MIT OCW problem sets! This problem also took me a while, but take my advice with a grain of salt as I am also new to programming. While your function works as intended, you should not need a helper function or that large amount of work to solve this problem. Reading through the suggested approach should lead you to a way to solve this problem more efficiently. Take a look at my solution which uses list comprehension.

def get_permutations(sequence):
    if len(sequence) == 1:
        return sequence
    else:
        first = sequence[0]
        r = sequence[1:]
        short = get_permutations(r)
        a = len(short)
        c=[]
        for j in range(a):
            c+=[short[j][0:i] + first + short[j][i:] for i in range(len(r)+1)]
        return c

Does my permutation function demonstrate a good use of recursion?

1 Answers1