Как осуществить поэлементное сравнение множества массивов друг с другом и создание нового массива из лучших пар, троек, четверок и т.д.?

Question

[Григорий Грибанов]

Дан массив массивов. Элементы только 0 и 1.
Необходимо сравнить каждый массив с каждым массивом, чтобы найти наибольшее количество совпадений мест элементов (в каких двух массивах единицы стоят почти на одних и тех же местах).
И важно вывести не просто парные значения (для этого алгоритм более-менне придумали), а все возможные, то есть сначала все лучшие пары, затем все лучшие тройки, затем четверки и так далее.

Comments

[Дмитрий]

нужен простой пример

[Григорий Грибанов]

Предположим мы запускаем производство множества разных стульев N. Для каждого стула существует уникальный набор основных материалов, однако всего материалов конечное число M. Чтобы сэкономить на ресурсах мы хотим запускать в производство только те виды стульев, которые лучше всего друг к другу подходят.
В массиве массивов находятся как раз эти сочетания стульев и материалов. Если по вертикали отложить модели стульев, а по горизонтали материалы, то получим матрицу с 0 и 1, где 0 - материал отсутствует, а 1 - материал присутствует (на данном этапе количество используемого материала не играет роли).
Нужно составить множество сочетаний. Сначала подобрать лучшие пары стульев, которые следовало бы производить вместе, если бы мы ограничились номенклатурой в два изделия. Затем все возможные тройки стульев, которые следовало бы производить вместе, если бы мы ограничились номенклатурой в три изделия и так далее.

[Григорий Грибанов]

Дмитрий, расписал выше. Если еще нужно пояснить, с радостью добавлю информации.

[Сергей Соколов]

что есть «лучшая пара»? Например, пара А: 1 совпадение 1 несовпадение

0 1 1 0
0 1 0 0

или пара Б: 2 совпадения, 2 несовпадения

0 1 1 1
1 1 1 0

Какая пара предпочтительнее и почему?

[Wataru]

Григорий Грибанов, Формализуйте, пожалуйста, метрику. Как понять, какая пара лучше другой? Приведите формулу или алгоритм сравнения. Например, можно считать количество совпавших единиц. Где больше - та пара и лучше. Или можно считать количество совпавших элементов (и нули, и единицы). Или считать количество совпавших единиц минус количество несовпадений. Но это для пар. Что делать с тройками стульев? С четверками стульев? Например, можно брать минимальное значение метрики для любой пары в группе. Или среднее. Или среднее среди квадратов. Можно считать, сколько материалов используются одновременно во всех стульях группы. Или более половины стульев. Можно еще много как считать. Все это - разные задачи.

Потом, вам надо вывести все сочетания? Или только несколько (или одно) лучшее?

В общем случае ничего лучше полного перебора всех сочетаний нет. Но для какой-то конкретной метрики возможно существуют оптимизации.

[Григорий Грибанов]

wataru, лучшая пара/тройка/четверка... та, у которой больше совпадений по единицам (по наличию материала). Выводить нужно все сочетания в порядке убывания:
У нас есть 10 моделей стульев: 1, 2, ..., 10
После первого прогона алгоритма получилась такая комбинация:
1.2,3,4,5,6,7,8,9,10
2.4,5,6,7,8,1,9,10
...
Это означает, что для 1 стула лучше всего подходит стул 2, то есть у них больше всего совпадения материалов. Следующая по количеству совпадений пара 1 и 3 и так далее. Если количество совпавших единиц одинаковое, то смотрим по количеству несовпадений (чем их меньше, тем лучше). Это только для стула 1.
Для стула 2 идеальная пара 4, потом больше всего подходит 5, потом 6 и т.д.
И вот так для всех 10-ти стульев. Потом необходимо создать то же для троек стульев, четверок и так далее.
Я пока тоже ничего лучше кроме полного перебора не нашел. Точнее даже более-менее понятно, как для пары стульев такое запрограммировать, но как для 3,4-х и так далее - не ясно.

[Григорий Грибанов]

Сергей Соколов, В приоритете максимальное количество совпадений по единицам (по наличию материала). Если одинаковое количество совпадений, то смотрим минимальное количество несовпадений (то есть где у одного массива 0, у второго 1).

[Григорий Грибанов]

Сергей Соколов, в вашем примере лучше пара Б, так как там больше совпадений. Если в примере А будет еще одно совпадение и 1 несовпадение, то приоритет отдается ему, так как по количеству совпадений они равны.

[Дмитрий]

Григорий Грибанов, Вы вероятно не очень понимаете значение словосочетания "простой пример". То что вы привели не является ни простым, ни примером

Answer 1

[Сергей Соколов]

Если я правильно понял, есть двумерная таблица единиц и нулей, например

0 1 0 0 1 1 1 0
0 0 1 0 1 1 1 0
1 1 1 0 0 1 1 0
1 1 0 0 1 1 1 0

и хочется получить максимальные «островки» единиц.
Не обязательно сплошных. Такие наборы строк и столбцов, где все единицы.
Вроде бы это задача поиска максимальной биклики в двудольном графе.

В примере это будет, наверное, строки [0, 1, 3] и столбцы [1, 5, 6] весом, соотв., 3 x 3 = 9