Problem Statement A traveling salesman must visit five cities. Determine the order of visits that minimizes total travel time.

Analysis Direct Solution Enumerate all posisble visit orders and compute the shortest time. This reduces to generating all permutations of five cities. Label the cities as {0, 1, 2, 3, 4}. The number of permutations is 5! = 120.

Programming Perspective Recursive Method Use recursion to explore unvisited cities at each step. Termination condition: all cities visited. Recursive step: iterate over unvisited cities, mark one as visited, and recurse.

Python Implementation

def generate_permutations(visited, step=0):
    """visited: list where index is city, value is visit order (-1 if unvisited)"""
    count_visited = 0
    for i, status in enumerate(visited):
        if status == -1:
            new_visited = list(visited)
            new_visited[i] = step
            generate_permutations(new_visited, step + 1)
        else:
            count_visited += 1
    if count_visited == len(visited):
        global permutation_count
        permutation_count += 1
        print(visited)

Lexicographic Order Method Concept Treat each permutation as a unique number (e.g., 01234) and generate them in ascending order. Smallest permutation: 01234, largest: 43210.

Algorithm

1. Start from the smallest permutation.
2. Find the next permutation by:
   • Scanning from right to left to find the first position where element is less then the next.
   • Swap this element with the smallest larger element to its right.
   • Reverse the sequence to the right of this position to get the smallest suffix.
3. Repeat until the largest permutation is reached.

Proof of Completeness This method ensures all permutations are generated without gaps by maintaining lexicographic order and minimal changes.

Python Implemantation

def next_permutation(seq):
    n = len(seq)
    i = n - 2
    while i >= 0 and seq[i] >= seq[i + 1]:
        i -= 1
    if i < 0:
        return None
    j = n - 1
    while seq[j] <= seq[i]:
        j -= 1
    seq[i], seq[j] = seq[j], seq[i]
    seq[i + 1:] = reversed(seq[i + 1:])
    return seq

def generate_lexicographic():
    perm = [0, 1, 2, 3, 4]
    while perm is not None:
        print(perm)
        perm = next_permutation(perm)

Base-Number Filtering Method Concept Generate all base-5 numbers from 0 to 43210 and filter out those with duplicate digits.

Algorithm

1. Iterate through base-5 numbers from 0 to the maximum.
2. Check each number for duplicate digits.
3. Output numbers without duplicates as valid permutations.

Python Implementation

def has_duplicates(num_list):
    freq = [0] * len(num_list)
    for digit in num_list:
        freq[digit] += 1
        if freq[digit] > 1:
            return True
    return False

def generate_base5():
    base = 5
    max_val = int('43210', base)
    for i in range(max_val + 1):
        digits = []
        temp = i
        for _ in range(base):
            digits.append(temp % base)
            temp //= base
        digits.reverse()
        if not has_duplicates(digits):
            print(digits)