Determine lowest value in row & column of an NxN array

Viewed 122

I have a list of lists that I have used to store the distances between objects.

The table looks something like this:

+----------+----------+----------+----------+----------+
|          | Object_A | Object_B | Object_C | Object_D |
+----------+----------+----------+----------+----------+
| Entity_E |     2    |     3    |     6    |     1    |
+----------+----------+----------+----------+----------+
| Entity_F |     3    |     4    |     7    |     2    |
+----------+----------+----------+----------+----------+
| Entity_G |     9    |     1    |     2    |     3    |
+----------+----------+----------+----------+----------+

The numbers represent the distance between the row & column header.

This was calculated roughly as follows:

entites = [Entity_E, Entity_F, Entity_G]
objects = [Object_A, Object_B, Object_C, Obhect_D]
distances = []

for object in objects:

    distanceEntry = []

    for entity in entities:
        distance = getDistance(entity, object)

        distanceEntry.append(distance)
    distances.append(distanceEntry)

This gave me roughly the information in the table above.

What I am looking to do is basically find the closest object to each entity (or vice versa). Each object or entity can only be matched with one other, and it should be based on proximity.

They way I have done this right now is by simply ordering the nested lists by size in distances (in the full code I have a way of determining which object is associated with each distance).

So, in doing that I would create the following associations:

+----------+----------+----------+
| Entity   |  Object  | Distance |
+----------+----------+----------+
| Entity_E | Object_D |     1    |
+----------+----------+----------+
| Entity_F | Object_D |     2    |
+----------+----------+----------+
| Entity_G | Object_B |     1    |
+----------+----------+----------+

This is incorrect because it associates Object_D twice.

The association should be:

+----------+----------+----------+
| Entity   |  Object  | Distance |
+----------+----------+----------+
| Entity_E | Object_D |     1    |
+----------+----------+----------+
| Entity_F | Object_A |     3    |
+----------+----------+----------+
| Entity_G | Object_B |     1    |
+----------+----------+----------+

This is where I am struggling - I can't figure out the best way to code logic for this.

Since Entity_E is closer to Object_D, it should get the association. So, for Entity_F, I need to take the second closest.

I was thinking about doing something where I record which Objects have already been assigned, or trying to do something where I match the min values in each column first, but they all seem to run into problems.

Is there a matrix operation or some kind of matrix math I could use to do this calculation?

Any advice would be much appreciated!

Edit - Added Full Code:

# Create an array that stores the distances between each label and symbol. Only calculate the distance for label that
# are "in front" of the symbol.
# Example Table:
# +---------------+--------------+--------------+--------------+--------------+
# |               |    Label_1   |    Label_2   |    Label_3   |    Label_4   |
# +---------------+--------------+--------------+--------------+--------------+
# | Measurement_1 |       2      |       3      | Not_in_front |       1      |
# +---------------+--------------+--------------+--------------+--------------+
# | Measurement_2 |       3      |       4      |       1      | Not_in_front |
# +---------------+--------------+--------------+--------------+--------------+
# | Measurement_3 | Not_in_front | Not_in_front |       2      |       1      |
# +---------------+--------------+--------------+--------------+--------------+

# Data Structures:
# measurementsDictionary = {['Type', 'Handle', 'X-Coord', 'Y-Coord', 'Z-Coord', 'Rotation', 'True Strike']}
# dipsDictionary = {['Handle', 'Text', 'Unit', 'X-Coord', 'Y-Coord', 'Z-Coord']}

#The two functions below grab the information from a csv-like file.
measurementsDictionary = getMeasurementsInformationFromFile()
dipsDictionary = getDipsInformationFromFile()


exportHeaders = [" "]
exportArray = []

for measurementSymbol in measurementsDictionary:

    measurementEntry = measurementsDictionary[measurementSymbol]
    measurementCoord = [measurementEntry[2], measurementEntry[3]]
    measurementDistance = []
    measurementDistance.append(measurementEntry[1])
    measurementCartesianAngle = getCartesianAngle(measurementEntry[6])
    measurementLineEquation = generateLineEquation(measurementCoord,measurementCartesianAngle)

    for dip in dipsDictionary:
        dipEntry = dipsDictionary[dip]
        dipCoord = [dipEntry[3],dipEntry[4]]
        isPointInFrontOfLineTest = isPointInFrontOfLine(measurementCartesianAngle, measurementLineEquation, dipCoord)

        if isPointInFrontOfLineTest == 1:
            measurementSymbolDistance = calculateDistance(measurementCoord, dipCoord)
            # string = dipEntry[0] +":" + str(measurementSymbolDistance)
            # measurementDistance.append(string)
            measurementDistance.append(measurementSymbolDistance)
        elif isPointInFrontOfLineTest == 0:
            string = ""
            measurementDistance.append(string)
    exportArray.append(measurementDistance)

for dip in dipsDictionary:
    dipEntry = dipsDictionary[dip]
    exportHeaders.append(dipEntry[0])

exportedArray = [exportHeaders] + exportArray
export = np.array(exportedArray)
np.savetxt("exportArray2.csv", export, fmt='%5s', delimiter=",")
print(exportHeaders)
1 Answers

I made some code to solve a similar problem to this a while back for PE345. I'm going to use my own array for this:

[[1,2,3],
 [4,5,6],
 [7,8,9]]

What you wanna do is get the cost of choosing a particular element. Do this by finding the cost of choosing a row, adding the cost of choosing a column, then subtracting the cost of choosing the element itself. So in my array, the cost of choosing element [0][0] is (1+2+3)+(1+4+7)-3*(1). I summed row 0, summed column 0, then subtracted out the element itself.

Now you have the cost of choosing each element. Find the element with the highest cost. That will be the lowest value in the grid. Choose it and make sure no other value in the row or column can be chosen. Repeat until a value in every row and column has been chosen.

Here's the source code from my project. Note that it finds the highest values, not the lowest.

from random import randint
from itertools import permutations
def make_a_grid(radius=5,min_val=0,max_val=999):
  """Return a radius x radius grid of numbers ranging from min_val to max_val. 
    Syntax: make_a_grid(radius=5,min_val=0,max_val=999
  """
  return [[randint(min_val,max_val) for i in xrange(radius)] for j in xrange(radius)]
def print_grid(grid,rjustify = 4):
  """Print a n x m grid of numbers, justified to a column.
    Syntax: print_grid(grid,rjustify = 4)
  """
  for i in grid:
    outstr = ''
    for j in i:
      outstr += str(j).rjust(rjustify)
    print outstr
def brute_search(grid):
  """Brute force a grid to find the maximum sum in the grid."""
  mx_sum = 0
  for r in permutations('01234',5):
    mx_sum = max(sum([grid[i][int(r[i])] for i in xrange(5)]),mx_sum)
  return mx_sum
def choose(initial_grid,row,col):
  """Return a grid with a given row and column zeroed except where they intersect."""
  grid = [sub[:] for sub in initial_grid] #We don't actually want to alter initial_grid
  Special_value = grid[row][col] #This is where they intersect.
  grid[row] = [0]*len(grid[row]) #zeroes the row.
  for i in xrange(len(grid)):
    grid[i][col] = 0
    grid[row][col] = Special_value
  print_grid(grid)
  return grid
def smart_solve(grid):
  """Solve the grid intelligently.
  """
  rowsum = [sum(row) for row in grid] #This is the cost for any element in a given row.
  print rowsum
  colsum = [sum(row) for row in [[grid[i][j] for i in xrange(len(grid))] for j in xrange(len(grid[0]))]] #Cost for any element in a given column
  print colsum,"\n"
  total_cost = [map(lambda x: x+i,rowsum) for i in colsum] #This adds rowsum and colsum together, yielding the cost at a given index.
  print_grid(total_cost,5)
  print "\n"
  #Total_cost has a flaw: It counts the value of the cell twice. It needs to count it -1 times, subtracting its value from the cost. 
  for i in xrange(len(grid)): #For each row
    for j in xrange(len(grid[0])): #For each column
      total_cost[i][j] -= 3*(grid[i][j]) #Remove the double addition and subtract once.
  ###Can I turn ^^that into a list comprehension? Maybe use zip or something?###
  print_grid(total_cost,5)
  return total_cost
def min_value(grid):
  """return the minimum value (And it's index) such that value>0.
     Output is: (value,col,row)"""
  min_value,row,col = grid[0][0],0,0
  for row_index,check_row in enumerate(grid):
    for col_index,check_val in enumerate(check_row):
      #print "Min_value: %d\n Check_Val: %d\n Location: (%d,%d)"%(min_value,check_val,row_index,col_index)
      if min_value>check_val>0:
        min_value = check_val
        row = row_index
        col = col_index
  return (min_value,row,col)
Related