interview-questions/recursion/permute.py

# Compute all permutations of a string

def permute(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    def insert_at_i(l, c, i ):
        """insert char c at location i of list l."""
        sub_start = l[:i]
        sub_end = l[i:]
        return sub_start + [c] + sub_end

    def rec_per(char):
        if len(nums) == 0:
            return [[char]]
        prev = rec_per(nums.pop())
        ans = []
        for i_l in prev:
            for i in range(len(i_l)+1):
                ans.append(insert_at_i(i_l,char,i))
        print(ans)
        return ans
    return rec_per(nums.pop())