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

Группировка большого количества массивов по наличию общих значений

Метки: [без меток]
2014-06-06 14:14:41 [обр] Дмитрий[досье]

Здравствуйте!

Есть массивы вида:
A = Array (
            [0] => a1,
            [1] => a2,
            [2] => a3,
            [3] => a4,
            [4] => a5,
            [5] => a6,
            [6] => a7,
            [7] => a8,
            [8] => a9,
            [9] => a10
);

B = Array (
            [0] => a11,
            [1] => a2,
            [2] => a12,
            [3] => a13,
            [4] => a14
);

C = Array (
            [0] => a15,
            [1] => a16,
            [2] => a1,
            [3] => a17,
            [4] => a2,
            [5] => a18,
            [6] => a19,
            [7] => a3
);

Массивов много - сотни или даже тысячи.

Нужно получить новый массив, каждый элемент которого - названия массивов, у которых есть хотя бы 3 общих элемента.
Например, в примере у A и B общий элемент только один, а у A и C общих элементов три.
На выходе должно получиться что-то такое:

Result = Array (
   [0] => Array (
      [0] => A,
      [1] => C
   )
)

Алгоритм должен быть жадным, т.е. добавлять максимальное количество исходных массивов в результат.
Например, если есть 3 массива A, B, С; у A и B - 4 общих элемента, у B и С - 4 общих элемента, а у A, B и С - три общих элемента, на выходе должна остаться только эта тройка.

Как в принципе подступиться к задаче?
Если можно, в терминах PHP.

Заранее спасибо!

спустя 4 часа 34 минуты [обр] Jared(0/26)[досье]

Вам надо, скажем, для массива А найти все массивы, которые пересекаются с А как минимум в трех элементах?
Берете А и затем для каждого следующего массива ищете пересечения.
Затем берете Б и затем для каждого следующего массива ищете пересечения.

В чем сложность то?

спустя 13 минут [обр] Дмитрий[досье]
Нужно сделать максимально большие группы.
Взять один и циклом пройтись по остальным - просто.
Допустим, у нас 1000 массивов.
Первый шаг - берем всю тысячу и ищем пересечение всей тысячи. Если размер пересечения меньше трех, значит, всю 1000 в одну группу не запихнуть. Идем дальше.
Второй шаг - выкидываем из тысячи первый и ищем пересечение остальных 999. Если размер пересечения больше трех, значит, все 999 можно засунуть в одну группу, если нет - возвращаем в тысячу первый и выкидываем второй... и т.д. Если подходящих пересечений нет - 1000 операций.
Третий шаг - выкидываем из первых 999, рожденных на втором шаге, первый элемент... и т.д.
Во-первых, получается очень сложно, во-вторых, расчет будет длится часами.
Да и мозгов не хватает запрограммировать. Интуитивно чувствую, что тут должна быть рекурсия, а как реализовать - не понимаю.
Наверняка есть какие-то другие пути, кроме перебора?!
спустя 1 день 18 часов [обр] Maus(0/3)[досье]

Дмитрий[досье]
Мне путь Jared[досье] нравится больше, распишу своё представление о нём подробнее:

  1. Находим последовательно пересечения A с B, A с C, ... B с С, ... , получаем наборы: [AB, AC, AD, AE, ...], [BC,BE,...], [CD,CE,...],... . Пересечения размером меньше 3 в набор не попадают
  2. теперь для каждого набор вычисляете новые наборы [ABC, ABD, ABE, ...], [ACD,AED, ] . Вот вам и рекурсия.

Вопросов два:

  1. как остановиться. Если на этой итерации пересечение получилось пустым - надо сохранить состояние предыдущей итерации и как-то отметить тот факт, что тут итерироваться уже не надо.
  2. как правильно сравнить остатки - они же будут на разных уровнях вложенности.

Запахло map-reduce ...

Powered by POEM™ Engine Copyright © 2002-2005