Поиск оптимального пересечения сотен массивов

[Puhovoi]

Доброго времени суток!

Раздумываю над задачей, суть такова:

дан одномерный массив чисел, скажем, на 100 элементов. Также даны еще 1000 таких же массивов, все с разными числами на борту, разумеется.

Что необходимо - найти 8 или N элементов исходного массива, которые бы присутствовали в максимальном количестве остальных массивов.

Прошу помощи в решении задачи, пока мыслей никаких.

С уважением.

[009]

диапазон чисел в массивах какой?
язык на котором собираетесь писать?

[Puhovoi]

Диапазон - не фиксирован. На Delphi.

[BDA]

Предположу:
Сортируем исходный массив по возрастанию
Заводим массив для учета количества
Проходим по остальным массивам и ищем число бинарным поиском в исходном
Если нашли, то увеличили счетчик (наверное, имеет смысл увеличивать его только 1 раз для каждого массива, то есть ставить флаг, что такое число уже встречалось в текущем массиве)
После прохода всех массивов сортируем исходный массив по количеству встреч
Выводим необходимое количество элементов из него

[009]

Сообщение от BDA

Предположу:
Сортируем исходный массив по возрастанию
Заводим массив для учета количества
Проходим по остальным массивам и ищем число бинарным поиском в исходном
Если нашли, то увеличили счетчик (наверное, имеет смысл увеличивать его только 1 раз для каждого массива, то есть ставить флаг, что такое число уже встречалось в текущем массиве)
После прохода всех массивов сортируем исходный массив по количеству встреч
Выводим необходимое количество элементов из него

может быть это самый быстрый способ )
Если считать, что элемент, встретившийся в одном массиве дважды и более засчитывается столько же раз, то здесь нужно рассмотреть два случая (какой быстрее):
- быстрая сортировка первого массива в 100 элементов, затем перебор 100*1000 элементов и бинарный поиск этих элементов в первом массиве
- быстрая сортировка 100*1000 элементов, затем бинарный поиск 100 элементов первого массива в отсортированном массиве [100*1000] (найдя такой элемент, вычислить сколько раз всего встречается не составит дальше труда).
Оценивать сложность приведенных алгоритмов не буду (никогда не любил, обычно практикой проверял)

[BDA]

Опять же предположу, что бинпоиск дешевле быстрой сортировки, поэтому первый вариант будет быстрее, но при правильной реализации легко протестировать оба варианта, просто написав пару циклов по-другому.

[Puhovoi]

Приведу пример, как в теории хочется, чтобы работало. Первая строка - исходный массив, нужно найти такие три числа, которые будут присутствовать в максимальном количестве других массивов. Т.е. перебрать все возможные комбинации, что есть, с учетом того, что исходный массив и дочерние состоят из 100+ абсолютно разных элементов.

84 51 87 23 57

94 10 88 48 32
50 44 65 60 21
37 32 34 88 10
60 94 30 18 27
27 89 78 31 14
67 23 84 51 43
32 78 98 29 96
11 69 84 51 23
30 45 91 93 29
28 10 29 56 93

Изначально думал сделать как:
- генерация NNNNN сочетаний из N чисел из исходного массива
- поиск во всех дочерних всех чисел из полученных сочетаний с записью, на какое сочетание больше всего 100%-х совпадений в дочерних массивах

Но тут случилось страшное - сочетаний для 80-элементного массива получается ровно 28.987.537.150. И это вот число сочетаний надо проверить по 1000 массивам, что крайне затруднительно. Собственно, затруднительно это еще на этапе генерации. А дочерних массивов на практике может быть и миллион.

P.s.: в приведенном выше примере всего 10 сочетаний, это еще терпимо. Вот далее уже, простите, полная задница.

[BDA]

Да уж, интересная задачка, нам нужен математик
Похоже, что Вы считаете некую статистику какой-то игры (чтобы найти наилучшие числа). Я угадал?

[Аватар]

Подозреваю, что для таких цифр решение задачи перебором не имеет практического смысла. В смысле время очень большое потребуется

[Puhovoi]

Да уж, не для моей технической базы...

BDA, не совсем. Эта задача встала в ходе оптимизации OCR.