a01_1_path_enumeration_algorithm.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Combinatorial Optimization - B.Korte, J.Vygen
Algorithm 1.1
Path Enumeration Algorithm
"""


def back_track(n):
    """Generate all permutations of 0 .. n-1"""

    # step 1: initialize
    p = range(n)
    yield p

    i = n - 2
    while i >= 0:
        # step 2: find 'k'
        aux = [False] * n
        for j in range(i):
            aux[p[j]] = True
        k = p[i] + 1
        while k < n and aux[k]:
            k += 1

        # step 3
        if k < n:
            p[i] = k
            if i == n - 1:
                yield p
            if i < n - 1:
                p[i + 1] = -1
                i += 1
        if k == n:
            i -= 1


def minimum_path(points):
    def distance(p, q):
        return max(abs(p[0] - q[0]), abs(p[1] - q[1]))

    ret = None
    n = len(points)
    for p in back_track(n):
        x = sum(distance(points[p[i]], points[p[i + 1]]) for i in range(n - 1))
        if not ret or x < ret[0]:
            ret = (x, [points[i] for i in p])
    return ret


if __name__ == '__main__':
    import itertools

    for x in back_track(4):
        print x
    print len(list(back_track(5)))

    # Using built-in function.
    for x in itertools.permutations(range(4)):
        print x

    print minimum_path([(1, 1), (5, 2), (1, 4), (3, 3), (4, 8), (2, 10)])