# Problem Set 4A
# Name: <Jordan>
# Collaborators:
# Time Spent: x:xx

def get_permutations(sequence):
    '''
    Enumerate all permutations of a given string

    sequence (string): an arbitrary string to permute. Assume that it is a
    non-empty string.  

    You MUST use recursion for this part. Non-recursive solutions will not be
    accepted.

    Returns: a list of all permutations of sequence

    Example:
    >>> get_permutations('abc')
    ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

    Note: depending on your implementation, you may return the permutations in
    a different order than what is listed here.
    '''
    

    # define a function to insert letter in a string list
    """
    for example, if i want to insert "x" in a string list ["gy", "po"]
    x has to insert in "gy": ["xgy", "gxy", "gyx"]
    
    my final desire output: ["xgy", "gxy", "gyx", "xpo", "pxo", "pox"]
    """
    def insert_letter(letter, string_list):
        result = []
        
        for i in range(len(string_list)):
            string_i = string_list[i]
            for i in range(len(string_i)+1):
                new_string = string_i[:i] + letter + string_i[i:]
                result.append(new_string)
        return result
    
    # determine the base -> only 1 letter left in the sequence    
    if len(sequence) == 1:
        return list(sequence)
    else:
        final_result = insert_letter(sequence[0], get_permutations(sequence[1:]))
    return final_result

            


if __name__ == '__main__':
#    #EXAMPLE
    example_input = 'abc'
    print('Input:', example_input)
    print('Expected Output:', ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
    print('Actual Output:', get_permutations(example_input))
    
#    # Put three example test cases here (for your sanity, limit your inputs
#    to be three characters or fewer as you will have n! permutations for a 
#    sequence of length n)

    example_input = 'hg'
    print('Input:', example_input)
    print('Expected Output:', ['hg', 'gh'])
    print('Actual Output:', get_permutations(example_input))
        
    example_input = 'dg'
    print('Input:', example_input)
    print('Expected Output:', ['dg', 'gd'])
    print('Actual Output:', get_permutations(example_input))