During the summer, my sister organized a high tea for her birthday. At the high tea, various friends from different friend groups were invited. To maximize the joy of her friends, she had to find a stable seating arrangement. What she didn't realize is that this is a interesting mathematical puzzle. For this puzzle, assume that the table is circular and each friend rated the other friends on a scale from 0 to 10, where 0 indicates someone they do not want as a neighbor. The goal is to find a seating arrangement such that the sum of satisfaction ratings for adjacent neighbors is maximized.

Graph representation§

After collecting the ratings of friends for each other, the data can be stored in a table. In this table, the labels of the rows represent the person giving the rating, and the columns represent the persons being rated. Each entry in the table corresponds to the rating a person gave to another person.

This table can be represented as a graph. In this graph, each friend represented as a vertex, and there is an arrow from friend $X$ to friend $Y$. Since friend $Y$ also rated friend $X$, there is also an arrow in the opposite direction.

Finding an optimal arangement is equivalent to finding a cycle containing all verticies. However, this poses a problem due to the directionallity of the arrows. For example Dila prefers to have Anne as her neighbor, but Anne doesn't share this preference. To address this, a choice must be made regarding weighting the preferences. In this case the decicion is made to take the minimum of the two ratings. To ensure that everyone has a neighbor they like. Which results into the following undirected graph.

Finding a cycle that maximizes the weights of the paths is equivalent to finding an optimal seating arrangement. Finding a cycle which maximizes the weights of the path is called the travelling salesman problem. This is a NP-hard for which we provided two possible solutions.

Python algorithm§

The two solutions provided are the brute-force search and Held–Karp algorithm, both solutions are exact algorithms. For both systems the graph needs to be represented into memory. For this the adjacency map is selected as it is easier to grasp and can store the bidirectionality of the raw data.

# Store the name of the vertices
vertices = ["A", "B", "C", "D", "E"]

# Initialize the adjacency map
graph = {i: {} for i in verticies}

graph["A"].update({"B": 3, "C": 8, "D": 3, "E": 10})  # Anne
graph["B"].update({"A": 0, "C": 4, "D": 4, "E": 3})  # Briseida
graph["C"].update({"A": 4, "B": 2, "D": 0, "E": 9})  # Candance
graph["D"].update({"A": 8, "B": 5, "C": 3, "E": 6})  # Dila
graph["E"].update({"A": 10, "B": 5, "C": 10, "D": 5})  # Eva

Then the following function is created to compute the distance between two verticies, which is the minimum rating between two friends.

def distance(x, y):
    return min(graph[x][y], graph[y][x])

Brute-force search§

Finding the optimal path using the brute-force method involves generating all possible unique cycle permutations and choosing the most desirable option. This approach is computationally expensive and has a computational time complexity of $O(n!)$. The permutations are generated in the following manner.

def permute(keys, k=0):
    number_of_keys = len(keys)
    if number_of_keys == k:
        yield keys
    else:
        for i in range(k, number_of_keys):
            keys[i], keys[k] = keys[k], keys[i]
            for permutation in permute(keys, k + 1):
                yield permutation
            keys[i], keys[k] = keys[i], keys[k]

Since cycles have the condition that the endpoint is the same as the start point, A subarray is created consisting of all elements except the beginpoint. Then all permutations of this subarray are generated to which the start/end point are added.

permutations = map(
    lambda x: verticies[0:1] + x + verticies[0:1], permute(verticies[1:], len(verticies)-1)
)

Then to find the most optimal arrangement, the permutation is selected which maximizes the sum of the edges.

max(
    permutations,
    key=lambda x: sum([distance(x[i - 1], x[i]) for i in range(1, len(x))]),
)

Which results into the following arrangement ADBCEA in string representation. With a some imagination it can be seen that this arrangement is isomorphic to a cycle and thus a valid seating arrangement.

Held–Karp algorithm§

The Held-Karp algorithm is a famous a dynamic programming algorithm used to solve this problem in a significantly faster manner. Instead of running in superexponential time complexity $O(n!)$ it runs in exponential time complexity $O(2^{n}n^{2})$. To apply this algorithm an make use of bitmasks the adjacency map is converted into an adjacency matrix and a combinations function is needed. To generate the adjecency matrix the following block of code is used:

def adjacency_matrix():
    V = len(verticies)
    matrix = [[0] * V for _ in range(V)]

    for i, v in enumerate(verticies, 0):
        for j, w in enumerate(verticies[i + 1 : V], i + 1):
            matrix[i][j] = matrix[j][i] = distance(v, w)
    return matrix

The last function which is used by Held-Karp is the combination function. Which is a function that generates all combinations of a given size. When generating combinations, there are two choices for each element: either the element is included $(1)$ or it is not $(0)$. By counting all the bits equal to one, the number of included elements is determined. This observation leads to the use of bitmasks.

def combinations(arr, size):
    n = len(arr)
    return [[arr[j] for j in range(n) if i & (1<<j)] for i in range(1<<n) if i.bit_count()==size]

An in-depth explanation of the Held-Karp algorithm is omitted, as it is left as an exercise for the reader.

def held_karp(matrix):
    V = len(matrix)
    C = {}

    # Initialize base cases: direct path from the starting vertex (0) to another vertex k
    # C[(1 << k, k)] holds the cost to reach vertex k directly from vertex 0 and the parent vertex (0)
    for k in range(1, V):
        C[(1 << k, k)] = (matrix[0][k], 0)

    # Iterate over subsets of increasing size, starting from size 2 up to V-1
    for subset_size in range(2, V):
        # Generate all subsets of the current size
        for subset in combinations(range(1, V), subset_size):
            bits = 0
        
            # Create a bitmask for the subset
            for bit in subset:
                bits |= 1 << bit
                

            # Calculate the minimum cost to reach each vertex k in the subset
            for k in subset:
                prev = bits & ~(1 << k) # Bitmask for the subset without vertex k

                res = []
                
                # Consider each vertex m in the subset (excluding the starting vertex 0 and the current vertex k)
                for m in subset:
                    if m == 0 or m == k:
                        continue
                    # Compute the cost of reaching k via m and store the result
                    res.append((C[(prev, m)][0] + matrix[m][k], m))
                C[(bits, k)] = min(res)

    # Bitmask for all vertices except the starting vertex 0
    bits = (2**V - 1) - 1

    res = []
    # Compute the minimum cost to return to the starting vertex 0
    for k in range(1, V):
        res.append((C[(bits, k)][0] + matrix[k][0], k))
    _, parent = min(res)

    # Set the starting vertex
    path = [0]

    # Reconstruct the optimal path
    for i in range(V - 1):
        path.append(parent)
        new_bits = bits & ~(1 << parent)
        _, parent = C[(bits, parent)]
        bits = new_bits

 
    # Return to the starting vertex
    path.append(0)

    return list(path)

Then the shortest path is computed as follows. Which yields the same arrangement of verticies ADBCEA.

list(map(lambda x : verticies[x], held_karp(adjacency_matrix(graph))))