skiena's backtracking

backtrack_permutations.py

def backtrack(A, k, N):
    """ General backtrack algorithm which enumerates all possible solutions """
    if is_a_solution(A, k, N):
        process_solution(A, k, N)
        return

    k = k + 1
    candidates = construct_candidates(A, k, N)
    for c in candidates:
        A[k-1] = c
        backtrack(A, k, N)


def is_a_solution(A, k, N):
    return k == N


def process_solution(A, k, N):
    print(A)


def construct_candidates(A, k, N):
    in_perm = [False for i in range(N+1)]
    for i in range(k):
        in_perm[A[i]] = True

    candidates = []
    for i in range(1, N+1):
        if not in_perm[i]:
            candidates.append(i)
    return candidates


def bt_permutations(N):
    A = [0 for i in range(N)]
    backtrack(A, 0, N)