46. Permutations

def permute(nums):
    """Recursive solution.
    every element ends up in each index f(n-1)x times, with f(n-1) = nb permutations of the elements left
    In other words: Take any number as the 1st element and append to it any permutation of the other numbers

    f(a)       = [a]
    f(a, b)    = [a, b],      [b, a]
               = [a] + f(b),  [b] + f(a)
    f(a, b, c) = [a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], [c, b, a]
               = [a] + f(b, c),        [b] + f(a, c),        [c] + f(a, b)    
    """
    def helper(nums, arr):
        nonlocal result

        if not nums:
            result.append(arr)
        for i, n in enumerate(nums):
            helper(nums[:i]+nums[i+1:], [n]+arr)

    result = []
    helper(nums, [])
    return result

def permute(nums):
    """Take any number as the first element and append to it any permutation of the other numbers """
    if not nums:
        return [[]]
    return [[n] + p for i, n in enumerate(nums) for p in permute(nums[:i] + nums[i+1:])]

def permute(nums):
    """Same solution as above but with generator"""
    def generator(nums):
        if not nums:
            return [[]]
        return ([n] + p for i, n in enumerate(nums) for p in generator(nums[:i] + nums[i+1:]))

    return list(generator(nums))

def permute(nums):
    """Alternative version of above solution"""
    def generator(nums):
        if not nums:
            yield []
        for i, n in enumerate(nums):
            for p in generator(nums[:i] + nums[i+1:]):
                yield [n] + p

    return list(generator(nums))

from functools import reduce

def permute(nums):
    """Use reduce to insert the next number anywhere in the already built permutations."""
    def helper(prev_res, n):
        result = []
        for permutation in prev_res:
            for i in range(len(permutation)+1):
                # insert the next number anywhere in the already built permutations
                result += [ permutation[:i] + [n] + permutation[i:] ]
        return result

    return reduce(helper, nums, [[]])

from itertools import permutations

def permute(nums):
    """Using the built-in methods permutations """
    return list(map(list, permutations(nums)))  # !! permutation returns itertools object
    # list(permutations) returns list of tuples (each permutations = tuple)
    # map(list, permutations()) convert each tuples into list but returns a map object