Permutation

def permutation(arr):
    '''
    input: [a, b, c]
    output: [[a, b, c], [a, c, b]
            [b, a, c], [b, c, a]
            [c, a, b], [c, b, a]]
    '''

    if not arr:
        return arr

    index_set = set()
    result = []
    buff = []
    permutation_helper(arr, buff, result, index_set)
    return result

def permutation_helper(arr, buff, result, index_set):
    # base case
    if len(buff) == len(arr):
        result.append(list(buff))
        buff = []
        return

    for i in xrange(0, len(arr)):
        if i in index_set:
            continue

        index_set.add(i)
        buff.append(arr[i])

        # recursion
        permutation_helper(arr, buff, result, index_set)

        buff.pop()
        index_set.remove(i)

if __name__ == '__main__':
    arr = ['a', 'b', 'c']
    result = permutation(arr)
    print result

Note:

• The time complexity = O(n!), n is the number of elements of the given array.

• The space complexity = O(n!), n is the number of elements of the given array

Permutation formula

http://www.mathwords.com/p/permutation\_formula.htm

For example:

n = 3, k = 3, the number of possible permutations is 6.

input: arr = ['a', 'b', 'c']

output: ['a', 'b', 'c'], ['a', 'c', 'b']

         \['b', 'a', 'c'\], \['b', 'c', 'a'\]

         \['c', 'a', 'b'\], \['c', 'b', 'a'\]

Note:

• 0! = 1
• 1! = 1