I am looking for a quick algorithm to determine a certain minimum property of a given 2D array - the sum of the smallest values that do not have rows or columns. I am sure that this should have a name, but I have no idea what he called.
I have a string matching system that splits the input string into spaces and compares it with the body of search values (also separated by spaces) and returns a matrix of distances between tokens within each string, and I want to reduce this to one cumulative distance using the minimum combination of distances that do not reuse a combination of input / output tokens.
Examples:
{ 1, 2 } => 5 (either 1+4, or 3+2) { 3, 4 } { 0, 2 } => 6 (because 2+4 < 0+8) { 4, 8 } { 1, 0, 0 } { 0, 1, 0 } => 0 { 0, 0, 1 } { 2, 3, 4 } { 3, 2, 4 } => 6 (2+2+2) { 4, 3, 2 }
The naive algorithm that I have used so far is as follows (C #):
public static int Minimux(this int[,] array) { var xUsed = new bool[array.GetLength(0)]; var yUsed = new bool[array.GetLength(1)]; var xMax = array.GetLength(0); var yMax = array.GetLength(1); var minima = new List<int>(); var limit = Math.Min(xMax, yMax); int xMin = 0, yMin = 0; while (minima.Count < limit) { var vMin = Int32.MaxValue; for (var x = 0; x < xMax; x++) { for (var y = 0; y < yMax; y++) { if (xUsed[x] || yUsed[y] || array[x, y] >= vMin) continue; vMin = array[x, y]; xMin = x; yMin = y; } } xUsed[xMin] = true; yUsed[yMin] = true; minima.Add(vMin); } return (minima.Sum()); }
It is basically an array of arrays, and when it finds each minimum value, it notes that the row / column combination is used as “used”, so it won’t be considered again - and as soon as it has as many minima as there are elements in the shortest dimension array, it returns the sum of these minima.
The problem is that it breaks down into the following cases:
{ 0, 0, 0 } { 0, 0, 0 } => 3 (when it should be returning 1) { 1, 2, 3 }
By the time the sweep reaches the last row, it has already designated columns 0 and 1 as “used,” and therefore the minimum unused value in row 2 is 3 , when it should actually use 1
Is there a standard algorithm for performing this operation?