Задачи на собеседовании в одну небезызвестную контору

[belugin]

http://www.codeplex.com/IronPython

import operator
def permutationStep(xs, i):
    rests = permutations(xs[:i] + xs[i+1:])  
    return map(lambda x:[xs[i]] + x, rests)
def sumLists(lists):
    return reduce(operator.add, lists, [])
def permutations(xs):
    if xs == []:
       return [[]]    
    return sumLists(map(lambda x: permutationStep(xs, x), range(len(xs)) ))
print permutations([1, 2])
print permutations([1, 2, 3])

[[1, 2], [2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Только так не честно, наверное