Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
skiena's backtracking
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.