notes/algorithms/combinatorial_search/code/perms.py at master · ailadson/notes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def generate_permutations(arr):
    n = len(arr)
    solution = [None] * n
    perms = []
    data = {
        'n' : n,
        'process' : lambda perm : perms.append(perm),
        'arr' : arr
    }
    backtrack(solution, -1, data)
    return perms

def backtrack(solution, step, data):
    if is_solution(solution, step, data):
        process_solution(solution, step, data)
    else:
        step += 1
        next_candidates = construct_next_candidates(solution, step, data)
        for i, next_candidate in enumerate(next_candidates):
            solution[step] = next_candidate
            backtrack(solution, step, data)

def is_solution(solution, step, data):
    return step == data['n'] - 1

def process_solution(solution, step, data):
    perm = map(lambda idx: data['arr'][idx], solution)
    data['process'](perm)

def construct_next_candidates(solution, step, data):
    in_perm = [False] * data['n']
    candidates = []

    for i in range(step):
        in_perm[ solution[i] ] = True

    for i in range(data['n']):
        if not in_perm[i]:
            candidates.append(i)

    return candidates

print generate_permutations(["cat", "dog", "bear", "lion", "fly"])