Based on this stackoverflow question.

Given a matrix find the highest sum by choosing elements such that no two have the same row or column.

Consider the following Matrix:

m1 m2 m3 n1 1 2 3 n2 4 5 6 n3 7 8 9 n4 10 11 12

The highest sum is 12+8+4 = 24

For the following:

m1 m2 n1 17 1 n2 18 15

The highest sum is 17+15 = 32.

For a reasonably small matrix you could just find all the combinations by taking one item from each column.

Here’s a c# implementation that solves the 3 column problem.

public void solve_3_cols() { var rows = new List<List<int>> { new List<int>{1,2,3}, new List<int>{4,5,6}, new List<int>{7,8,9}, new List<int>{10,11,12} }; var matrix = rows .SelectMany((x, row) => x.Select((y, col) => new { Row = row, Col = col, Value = y })) .ToList(); var sums = from c1 in matrix let lev1Cols = new HashSet<int>(new[] { c1.Col }) let lev1Rows = new HashSet<int>(new[] { c1.Row }) from c2 in matrix where !lev1Cols.Contains(c2.Col) && ! lev1Rows.Contains(c2.Row) let lev2Cols = new HashSet<int>(lev1Cols.Concat(new[]{c2.Col})) let lev2Rows = new HashSet<int>(lev1Rows.Concat(new[]{c2.Row})) from c3 in matrix where !lev2Cols.Contains(c3.Col) && !lev2Rows.Contains(c3.Row) select new { Sum = c1.Value + c2.Value + c3.Value, Items = new[] { c1, c2, c3 } }; var result = sums.OrderByDescending(x => x.Sum).First(); Console.WriteLine(result.Sum); result.Items.ForEach(Console.WriteLine); }

output:

24 { Row = 1, Col = 0, Value = 4 } { Row = 2, Col = 1, Value = 8 } { Row = 3, Col = 2, Value = 12 }

To solve a different number of columns change the way sums is being built. For example, here’s a variant that solves the 2-column example:

[Test] public void solve_2_cols() { var rows = new List<List<int>> { new List<int>{17,1}, new List<int>{18,15}, }; var matrix = rows .SelectMany((x, row) => x.Select((y, col) => new { Row = row, Col = col, Value = y })) .ToList(); var sums = from c1 in matrix let lev1Cols = new HashSet<int>(new[] { c1.Col }) let lev1Rows = new HashSet<int>(new[] { c1.Row }) from c2 in matrix where !lev1Cols.Contains(c2.Col) && !lev1Rows.Contains(c2.Row) select new { Sum = c1.Value + c2.Value, Items = new[] { c1, c2 } }; var result = sums.OrderByDescending(x => x.Sum).First(); Console.WriteLine(result.Sum); result.Items.ForEach(Console.WriteLine); }

output:

32 { Row = 0, Col = 0, Value = 17 } { Row = 1, Col = 1, Value = 15 }

If we were to introduce a couple of objects like *Cell* and *Sum* we could create a solver that works for a variable number of columns.

The rub is, finding all combinations is not a good solution for very large matrices.

on 26 January 2015 at 9:55 pm |Shrutscould you give solution in javascript or explain a bit more

Thanks

on 27 January 2015 at 8:05 am |handcraftsmanThe problem is to get the highest possible sum of values from a 2D array, while using each row AND column (array index) only once.

One solution is to get all the values from the array in order, with meta data, then start at the highest value and throw out all subsequent items from that same row and column. Similar to the Sieve of Eratosthenes. But, this isn’t guaranteed to provide the highest value because the first selection caused other values to be thrown out that together might have summed to a higher value.

Does that help?

on 29 January 2015 at 2:32 amShrutsYes Thank you