python – Heap’s algorithm applied for the assignment issue

I have studied the Munkres algorithm for a software and I have to implement a Python test which validates the result of the algorithm for a given squared matrix.

Context

Let mat be a n*n matrix. The assignment problem consists of finding a set of n matrix cells following 2 conditions:

  • There must be one cell per row and one cell per column
  • The sum of cells must hold the highest possible value.

The problem is equivalent of finding all column permutations of the matrix, then calculate the trace to check if this is the maximum value.

Algorithm

I used Heap’s algorithm to list all possible columns permutations in the matrix. More specifically:

  • The current matrix gives the first column permutation: its trace is saved as the current maximum value.
  • Heap’s algorithm is launched. Each time a new permutation is made, the resulting trace is updated, which will be stored as the maximum value if it is greater than the current value.

The interest for Heap’s algorithm is that there is only one interchange to make in order to find a new permutation, so the trace update is fast.

Problem

I implemented both versions of Heap’s algorithm (recursive and non-recursive) and I applied it in a 3×3, 4×4 and 5×5 matrix. The non-recursive version gives a good result whereas the recursive version gives a maximum value which is slightly different: for the 5*5 matrix, the value is 80 instead of 69. What could be the cause?

Code

import time

# 5*5 matrix
mat = ((1,2,3,4,5),(2,4,6,8,10),(20,16,12,8,4),(4,8,12,16,20),(5,10,15,20,25))
columns = (0,1,2,3,4)

# 4*4 matrix
# mat = ((1,2,3,4),(2,4,6,8),(20,16,12,8),(4,8,12,16))
# columns = (0,1,2,3)

# 3*3 matrix
# mat = ((1,2,3),(2,4,6),(12,8,4))
# columns = (0,1,2)

maximum = 0

def bestAssociation(mat):
    global maximum

    t0 = time.time()

    total = 0
    for k in range(len(columns)):
        total += mat(k)(columns(k))
   
    maximum = total
    total = heap(columns, len(columns), total) # Non-recursive version
    # total = recursive_heap(columns, len(columns), total) # Recursive version
 
    t1 = time.time()
    print
    print("max -> " + str(maximum))
    print("Time: " + str(t1 - t0) + "s")

def heap(columns, n, tot):
    compteur = (0) * n
    print(str(columns) + " -> " + str(tot))
    i = 0

    while i < n:
        if compteur(i) < i :
            if i % 2 == 0:
                tot = swap(columns, 0, i, tot)
            else:
                tot = swap(columns, compteur(i), i, tot)
            
            print(str(columns) + " -> " + str(tot))
            compteur(i) += 1
            i = 0
        else:
            compteur(i) = 0
            i += 1

    return tot

def recursive_heap(columns, n, tot):
    if n == 1:
        print(str(columns) + " -> " + str(tot))
    else:
        recursive_heap(columns, n - 1, tot)
        for i in range(0, n - 1):
            if n % 2 == 0:
                tot = swap(columns, i, n - 1, tot)
            else:
                tot = swap(columns, 0, n - 1, tot)

            recursive_heap(columns, n - 1, tot)

def swap(columns, i, j, tot):
    global maximum

    tot -= (mat(i)(columns(i)) + mat(j)(columns(j)))

    buf = columns(i)
    columns(i) = columns(j)
    columns(j) = buf

    tot += (mat(i)(columns(i)) + mat(j)(columns(j)))
    if (tot > maximum):
        maximum = tot

    # print("max -> " + str(maximum))

    return tot

bestAssociation(mat)
```