"""
 permutations_backtrack.py

 This is (essentially) Skienna's implementation of a permutation generator
 using backtracking (i.e. depth-first recursive search) from pg 232 of his text,
 translated into python.

 $ python permutations_backtrack.py 
 [0, 1, 2, 3]
 [0, 1, 3, 2]
 [0, 2, 1, 3]
 [0, 2, 3, 1]
 [0, 3, 1, 2]
 [0, 3, 2, 1]
 [1, 0, 2, 3]
 [1, 0, 3, 2]
 [1, 2, 0, 3]
 [1, 2, 3, 0]
 [1, 3, 0, 2]
 [1, 3, 2, 0]
 [2, 0, 1, 3]
 [2, 0, 3, 1]
 [2, 1, 0, 3]
 [2, 1, 3, 0]
 [2, 3, 0, 1]
 [2, 3, 1, 0]
 [3, 0, 1, 2]
 [3, 0, 2, 1]
 [3, 1, 0, 2]
 [3, 1, 2, 0]
 [3, 2, 0, 1]
 [3, 2, 1, 0]

 Jim Mahoney | April 2013 | MIT License
"""

# --- general purpose backtrack search algorithm ---

def backtrack(answer, data):
    """ A generic backtrack algorithm
        answer = [a1, a2, ..., ak] solution so far
        data   = anything else we need for the particular problem
    """
    # Skienna's variables :
    # a      (i.e. answer) is the vector that we're building
    # k      is len(answer), the index we're working on
    # S      is possible extensions to the answer
    # data   is anything else that we need to pass along.
    #
    ## print "backtrack answer='%s', data='%s'" % (str(answer), str(data))
    if is_a_solution(answer, data):
        process_solution(answer, data)
    else:
        for candidate in construct_candidates(answer, data):
            ## print " candidate = '%s'" % str(candidate)
            make_move(candidate, answer, data)   # e.g. answer.append(c)
            backtrack(answer, data)
            unmake_move(candidate, answer, data) # e.g. answer.pop()

# --- data and functions for backtrack permutations ---

data = {'N'         : 4,          # number of items to permute
        'remaining' : [True]*4,   # true for each digit not yet in answer
        }
answer = []

def is_a_solution(answer, data):
    return len(answer) == data['N']

def process_solution(answer, data):
    print answer

def construct_candidates(answer, data):
    return filter(lambda i: data['remaining'][i], range(data['N']))

def make_move(candidate, answer, data):
    answer.append(candidate)
    data['remaining'][candidate] = False

def unmake_move(candidate, answer, data):
    answer.pop()
    data['remaining'][candidate] = True

# --- and we're off! ---

backtrack(answer, data)