|
Всем привет!
Сразу хочу сказать что в математике я чуть более чем никак. Но встала такая задача передо мной...
Есть множество массивов одинаковой длины (допустим длиной 3):
[A4, B2, C2]
[A2, B8, С2]
[A9, B2, С1]
......много их короче
Мне необходимо сгруппировать, получить группы следующего вида
A1,A2;
B1;
C1,C2
Для создания данной группы в исходном множестве необходимо наличие массивов:
[A1, B1, C1]
[A1, B1, C2]
[A2, B1, C1]
[A2, B1, C2]
Т.е. наверное это можно назвать вычислением обратным декартовому произведению.
Некоторые массивы в результате могут вообще не войти ни в одну группу
Задачу решил, но как мне кажется совсем неэффективно. Простым перебором
Алгоритм примерно такой:
1. Выбираем первый массив из множества. Например [A1, B1]
2. Пытаемся сгруппировать первый и второй (скажем [A2, B2]), т.е. ищем [A1, B2] и [A2, B1].
3. Если нашли, то удаляем их из исходного множества и пытаемся по тому же принципу включить в полученную группу остальные массивы
4. Если не нашли, то берем 1-й и 3-й и пытаемся их сгруппировать...
Тестирование показало, что алгоритм выполняется до полутора минут для 15000 массивов размерности 5 (!!!). При этом по полной занимая одно ядро процессора:))
Может кто подскажет более эффективные способы решения подобной задачи?
|
