Xpoint
   [напомнить пароль]

Специальное пересечение списков. Обход графа?

Метки: [без меток]
2006-10-13 02:52:20 [обр] firestorm[досье]

Уважаемые!

Такая задачка:
Есть N списков (массивы разной длины). Все списки отсортированы.
(
  пример:
  Список1: 1,2,23,156,456,2001,19743
  Список2: 2,3,22,45,245,365,2566,19742
  Список3: 4,24,34,250,2345,19744
)
Нужно найти все такие N-ки (тройки), такие, чтобы расстояния между ними по вертикали были равны 1.
Для приведенного примера это тройки (2,3,4), (23,22,24), (19743,19742,19744)

Как эффективно организовать алгоритм?
Сравнение каждого с каждым считаю неэффективным - соответственно хочется организовать какой-то разумный обход.

В приведенном примере проходы такие (как мне кажется): (гориз, верт)
[1,1]->[1,2]->[1,3]->[1,2]->[2,1]->[2,2]->[1,3]->[2,3]->[2,2]->[2,1]-> до конца списка

и т.д
Это разумно?

Если да - как это формализовать?
Что-то я не могу придумать код...

Может быть есть какой-нибудь более толковый алгоритм (на основе какой-нибудь суммы элементов и вычитания списков,... - в порядке бреда)

Спасибо!

спустя 2 месяца 10 дней [обр] Ser_g(0/1)[досье]
можно проверить по такому условию: 1+2+3-(1*3) = 3
Powered by POEM™ Engine Copyright © 2002-2005