Какой алгоритм подойдет для наиболее оптимального решения задачи?

Question

[Виталий Ртищев]

Напишите функцию, принимающую массив из строк, содержащих номер телефона в формате +7 (XXX) XXX-XX-XX. Функция должна вернуть пары номеров, которые отличаются одной цифрой.

Например,

getPhonePairs([
  '[phone]',
  '[phone]',
  '[phone]',
]);

// ->
[
  ['[phone]', '[phone]'],
  ['[phone]', '[phone]'],
];

Comments

[Армянское Радио]

Начать можно с того, чтобы отсортировать все номера лексикографически.

[longclaps]

hint000, ты такой четкий... Но эту мелодию можно угадать с одной ноты.

[uvelichitel]

hint000,

критерии оптимальности?

- не делать полного перебора квадратичной сложности O(n**2). И это представляется возможным. Примем метрикой расстояния между номерами D(номер1, номер2) количество отличающихся цифр. Тогда, например, если D(N1, N2) >2 и D(N2, N3)<2 то обязательно D(N1, N3)>1, N1 можно не сравнивать с N3. То есть очевидно можно не сравнивать каждый с каждым, можно избежать полного перебора.

[longclaps]

uvelichitel, дорогой, ты тоже чоткий... но не надо меряться метриками. Покажи код.

[uvelichitel]

Виталий Ртищев задачка интересная, но может переформулируйте/уточните условие в заголовке. Например "Как выбирать из справочника похожие номера?". Тогда, мне кажется вы привлечете больше алгоритмистов. Вопросы заданные в такой общей и несодержательной форме как у вас многие просто не открывают...

[uvelichitel]

longclaps,

Покажи код.

Ага, USD35/час мой рейт, тогда код покажу.)) Я ж тоже чоткий...

[longclaps]

uvelichitel, не смеши мои тапочки. знаток хаскеля. Есть простое решение О(NlogN), и для его описания можно обойтись даже словами. За базар тоже USD35/час просишь?

[uvelichitel]

longclaps,

Есть простое решение О(NlogN)

Ну так приведите его хотя бы словами. Я плюсану. И на хабре могу вам плюсануть(у меня плюсовалка есть). На вопрос я подписался. Я понимаю что решение логарифмической сложности должно существовать. Мне это решение не известно, прежде чем искать его самому хочу послушать экспертов.

[longclaps]

uvelichitel, даже линейный есть, если за память не париться. Python

data = ['1234', '1235', '2237', '3237', '2238', '2239']
for i in range(4):  # длина номера
    pairs = {}
    for s in data:
        t = s[:i] + s[i + 1:]
        l = pairs.get(t, [])
        l.append(s)
        pairs[t] = l
    for l in pairs.values():
        if len(l) > 1:
            print(*l)

выхлоп

2237 3237
1234 1235
2237 2238 2239

[uvelichitel]

longclaps, Хорошо. Но кажется некорректно - попробуйте добавить '2337' в data.

[longclaps]

uvelichitel,

2237 3237
2237 2337
1234 1235
2237 2238 2239

[uvelichitel]

longclaps, Хорошо. Куда плюсануть?))

[longclaps]

uvelichitel, да не к спеху, будет нужно - позову )

Answer 1

[GreenBear]

Если два номера "похожи", значит у них есть ровно один отличающийся символ, который расположен в той же самой позиции. Это значит, если у всех номеров удалить символ из конкретной позиции, то все "похожие" номера станут идентичными между собой. А значит их можно собрать в словарь, где ключ - это урезанный номер, а значение - это массив неурезанных "похожих" номеров.

В номере 11 значащих символов. Убираем сначала у всех первый символ, получаем первый словарь с похожими номерами.
Потом из начальных номеров убираем второй символ, и получаем второй словарь с "похожими номерами" по второй позиции.
И так делаем 11 раз, пока у нас не получится 11 словарей.
Далее из каждого словаря остается выбрать только те значения, в которых более одного элемента в массиве.
Останется только составить пары номеров, взятых из этих массивов.

Такой алгоритм будет работать некорректно, если изначально есть полностью идентичные номера, но если я правильно понял, изначально они все разные.

Comments

[longclaps]

Толковое толкование. Я так, наверное, никогда не научусь. Но в комментариях к вопросу решение есть.
В любом случае с почином.

[GreenBear]

longclaps, спасибо! Только сейчас заметил, что у вопросов еще и комментарии есть.
У вас там все ч0тко!

[Дмитрий Макаров]

Прикольно!

Предлагаю докрутить. Из номеров будем не убирать символ, а заменять на "Х" - тогда нам будет нужен только один словарь. А перед тем как положить очередной номер в кучку похожих номеров, выдать пары между новым и лежащими в кучке.

Answer 2

[Дмитрий Макаров]

Положить все номера в хэш-таблицу.
start: Берем первый непомеченный номер и, начиная с него, делаем поиск в ширину по всем соседям (их меньше либо равно 20).
Если сосед найден, то выписываем эту пару.
Когда у очередного номера найдены все соседи, то помечаем его.
Следующую итерацию поиска проводим только для непомеченных соседей.
Повторяем, начиная со start`а, пока есть непомеченные номера.