Сгруппировать наиболее похожие элементы вместе

Question

У меня есть двумерный массив целых чисел, например:

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}
}

Я вообще не хочу изменять столбцы этого массива;Тем не менее, я хотел бы поменять строки так, чтобы наиболее похожие строки были сгруппированы вместе.Аналогично в этом случае означает наибольшее количество равных элементов.

Редактировать: Аналогичные строки означают, если в одной строке 1,2,3,4,5,6, а в другой 1,2, 3,4,9,10 Они имеют 4 сходства.

Какой лучший способ сделать это?

Примечание: наибольшее количество строк в моем массиве составляет около 100 инаибольшее количество элементов в каждой строке будет равно 10, поэтому сложность имеет значение, как указано!

Answer 1

Этот вопрос сводится к проблеме коммивояжера. Если вы думаете о каждой строке как о городе, а затем определяете некоторую функцию расстояния, которая вычисляет расстояние между двумя рядами. Вопрос в том, как упорядочить строки так, чтобы расстояние было минимальным. Эта проблема является NP-Complete и не может быть решена в разумные сроки за 100 строк. Решение для перебора для этого потребует O (N!) Вычислений. Существуют эвристические алгоритмы (алгоритмы, которые приближаются к лучшему ответу), которые решат это за разумное время.

Задача коммивояжера (Википедия)

Одним из примеров является использование жадного алгоритма. Выберите одну строку случайным образом, это строка 1. Затем выберите ближайшую строку для строки 1 в качестве строки 2. Затем выберите ближайшую строку для строки 2 в качестве строки 3. Выполните, пока не будут выбраны все строки. Это не очень оптимальное решение.

Answer 2

Я не эксперт по проверке алгоритмов, но я попробую помочь.Кроме того, я не тестировал это решение и не задумывался о нем более 15 минут, но думаю, что оно сработает или, по крайней мере, приблизит вас.Помните, что эвристические алгоритмы не на 100% верны :) Я рискну оказаться ниже 3K:

Сортировать каждую строку, чтобы таблица, вставленная вами после сортировки, выглядела так:* Теперь отсортируйте каждую строку по значениям в первом столбце каждой строки, чтобы результат выглядел следующим образом:

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