about summary refs log tree commit diff
path: root/scratch/facebook/recursion-and-dynamic-programming/permutations.py
blob: e23972d4186d1837027a66500908e23dc522e021 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
def char_and_rest(i, xs):
    return xs[i], xs[:i] + xs[i+1:]

# perms :: String -> [String]
def perms(xs):
    if len(xs) == 1:
        return [xs]
    result = []
    for c, rest in [char_and_rest(i, xs) for i in range(len(xs))]:
        result += [c + perm for perm in perms(rest)]
    return result

print(perms("cat"))