Group most similar elements together

Question

I have a two-dimensional array of ints, for example:

int [][] board=
{
{23,17,3,29,12,10},
{17,4,11,12,10,19},
{32,33,25,25,28,35},
{27,29,24,25,23,37},
{29,40,34,26,24,39},
{23,37,29,36,31,3}
}

I don't want to change the columns of this array at all; however, I would like to swap the rows so that the most similar rows are grouped together. Similar in this case means most number of equal elements.

Edit: Similar rows means, if one row has 1,2,3,4,5,6 and another has 1,2,3,4,9,10 They have 4 similarities.

What's the best way to do this?

Note: the most number of rows I will have in my array is around 100 and the most number of elements in each row will be 10 so the complexity does matter as pointed out!

Answer 1

This question reduces to the traveling salesman problem. If you think of each row as being a city and then define some distance function which computes the distance between two rows. The question is how to order the rows so that the distance is minimized. This problem is NP-Complete and cannot be solved in a reasonable amount of time for 100 rows. The brute-force solution for this would require O(N!) computations. There are heuristic algorithms (algorithms that get close to the best answer) that will solve this in a reasonable time.

Traveling Salesman Problem (Wikipedia)

One example is to use a greedy algorithm. Choose one row at random, this is row 1. Then choose the closest row to row 1 as row 2. Then choose the closest row to row 2 as row 3. Run until all the rows are chosen. This is not a very optimal solution.

Answer 2

I'm not an expert on proving algorithms, but I'll take a shot at helping. Also, I haven't tested this solution or given it more than 15 minutes of thought, but I think it will work or at least get you close. Remember heuristic algorithms are not 100% correct :) I'll take the risk of being down below 3K:

Sort each row, so the table you pasted after sorting looks like:

3,  10, 12, 17, 23, 29
4,  9,  10, 11, 12, 17
25, 25, 28, 32, 33, 35
23, 24, 25, 27, 29, 37
24, 26, 29, 34, 39, 40
3,  23, 29, 31, 36, 37

Now sort each row by the values in the first column of each row, so the result looks like:

3,  10, 12, 17, 23, 29
3,  23, 29, 31, 36, 37
4,  9,  10, 11, 12, 17
23, 24, 25, 27, 29, 37
24, 26, 29, 34, 39, 40
25, 25, 28, 32, 33, 35