Получил недавно любопытное задание на интервью. Вот текст задания:

Anagrams are defined as words with the same length and same number of characters in any order.
Eg:
bat/tab/abt are anagrams
aabb/baba/bbaa/abab — anagrams
abcd/abce — are not anagrams (different characters)
aaab, aabb — are not anagrams (different character count)

Given a list of words — { abcd, bbb, abc, bat, cat, yyyyxxxx, tab, atb, rat, cab, xxyyxxyyxx, atb }
Print out the anagram pairs — {{abc, cab}, {bat, tab, atb, atb}}

Assuming that the input is of type [a-z], can you optimize the solution.

С анаграммами всё просто — они легко находятся, если сравнивать отсортированные копии строк. А вот с оптимизацией я так и не разобрался. Я так понимаю, смысл там в генерации уникального хэша для каждой строки, но как сделать хэш одинаковым для разных строк, содержащих тот же набор букв, я пока не понял.
Коллега взглянул и сказал, мол, "о, тут всё просто — надо использовать простые числа". Если я правильно понимаю, в этом варианте нужно выбирать простые числа от 2 и более (а может и от 3, не уверен) и брать результат умножения. Но 26-е простое число в этом варианте будет 101, т.е. для каждого 'z' нам нужно умножать хэш на 101. Тогда 6..7 букв 'z' дадут хэш, который вылезет за пределы 64 bit.

Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?

Здравствуйте, Artem Korneev, Вы писали:

AK>Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?

hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]

Здравствуйте, kov_serg, Вы писали:

AK>>Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?

_>hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]

Не, ну бита там явно не хватит, нужен учёт количества символов. Бит даст одинаковый хэш для "ab" и "baaab" — слишком много коллизий.

Здравствуйте, Artem Korneev, Вы писали:

AK>Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?
А как насчёт: отсортировать массив, используя в качестве компаратора сравнение строк, в которых символы предварительно сортируются. А потом пройтись по этому массиву и сразу выдать парные — они будут распологаться рядом.

Здравствуйте, Artem Korneev, Вы писали:

AK>Здравствуйте, kov_serg, Вы писали:

AK>>>Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?

_>>hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]

AK>Не, ну бита там явно не хватит, нужен учёт количества символов. Бит даст одинаковый хэш для "ab" и "baaab" — слишком много коллизий.
У "ab" length=2, а у "baaab" length=5. Где коллизии?

Здравствуйте, kov_serg, Вы писали:

_>>>hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]
AK>>Не, ну бита там явно не хватит, нужен учёт количества символов. Бит даст одинаковый хэш для "ab" и "baaab" — слишком много коллизий.
_>У "ab" length=2, а у "baaab" length=5. Где коллизии?

Я на length в конце внимания не обратил.
Коллизии будут у строк одинаковой длины с одинаковым набором используемых символов, "aaaab" и bbabb", например.

Здравствуйте, ·, Вы писали:

·>А как насчёт: отсортировать массив, используя в качестве компаратора сравнение строк, в которых символы предварительно сортируются.

Дополнительная сортировка массива ухудшает параметры этого алгоритма. Там итоговое быстродействие будет умножено на log(n), где n — кол-во строк. Ибо сортировка всяко медленнее, чем простой одноразовый проход по списку строк.
Ничего лучше, чем просто проход по всем строкам и раскидывание строк по словарю, где ключом будет хэш отростированной строки, там уже не придумаешь. Проблема только в скорости генерации этого хэша. Для сортировки строки мы имеем m * log (m), где m — кол-во символов в строке.

Сейчас взбрёл мне в голову мысль, что вот для сортировки строки мы можем использовать какой-нибудь bucket sort, дающий линейное время сортировки, но пригодный только для небольшого количества элементов. Вот наверное это-то и имелось в виду. Хм..

Здравствуйте, Artem Korneev, Вы писали:

AK>Здравствуйте, kov_serg, Вы писали:

_>>>>hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]
AK>>>Не, ну бита там явно не хватит, нужен учёт количества символов. Бит даст одинаковый хэш для "ab" и "baaab" — слишком много коллизий.
_>>У "ab" length=2, а у "baaab" length=5. Где коллизии?

AK>Я на length в конце внимания не обратил.
AK>Коллизии будут у строк одинаковой длины с одинаковым набором используемых символов, "aaaab" и bbabb", например.
Тогда приводи к каноническому виду и считай обычный хэш. Например cортируешь анаграмму "bbaabb" -> aabbbb -> string_hash(aabbbb)

Здравствуйте, Artem Korneev, Вы писали:

AK>С анаграммами всё просто — они легко находятся, если сравнивать отсортированные копии строк. А вот с оптимизацией я так и не разобрался. Я так понимаю, смысл там в генерации уникального хэша для каждой строки, но как сделать хэш одинаковым для разных строк, содержащих тот же набор букв, я пока не понял.
AK>Коллега взглянул и сказал, мол, "о, тут всё просто — надо использовать простые числа". Если я правильно понимаю, в этом варианте нужно выбирать простые числа от 2 и более (а может и от 3, не уверен) и брать результат умножения. Но 26-е простое число в этом варианте будет 101, т.е. для каждого 'z' нам нужно умножать хэш на 101. Тогда 6..7 букв 'z' дадут хэш, который вылезет за пределы 64 bit.

Умножение — не проблема.
Во-первых, хеш в хеш-таблице всё равно обрезается до количества корзин (остаток от деления). Так что пофиг на переполнение.
Во-вторых, в кольце по модулю 2**64 умножение будет долго давать уникальные числа.

А вот для быстрого сравнения в рамках одной корзины — есть смысл рядом со строкой держать ещё один хеш, посчитанный другим способом. Хотя бы и битсет входящих букв.
Держать рядом с каждой строкой её отсортированную версию (или вектор счётчиков), или устроить такую структуру данных: хеш -> сортированная строка -> список реально найденных анаграмм, — это избыточно по памяти.
Ведь есть риск, что большинство строк появятся единожды, т.е. мы на ровном месте поднимем двукратный рост памяти.

Здравствуйте, Artem Korneev, Вы писали:

AK>А вот с оптимизацией я так и не разобрался. Я так понимаю, смысл там в генерации уникального хэша для каждой строки, но как сделать хэш одинаковым для разных строк, содержащих тот же набор букв, я пока не понял.
XOR всех символов в качестве хэша, а потом сравнение только в пределах полученных бакетов.

Здравствуйте, Artem Korneev, Вы писали:

AK>Здравствуйте, kov_serg, Вы писали:

_>>>>hash=[ bit0=has(a), bit1=has(b), ... bit(25)=has(z), bit(26..31)=length ]
AK>>>Не, ну бита там явно не хватит, нужен учёт количества символов. Бит даст одинаковый хэш для "ab" и "baaab" — слишком много коллизий.
_>>У "ab" length=2, а у "baaab" length=5. Где коллизии?

AK>Я на length в конце внимания не обратил.
AK>Коллизии будут у строк одинаковой длины с одинаковым набором используемых символов, "aaaab" и bbabb", например.

Вариант который вам предлагал колега чем не понравился? Что-то вида:

int code(char c) {
    if (c>='a' && c<='z') return c-'a';
    if (c>='A' && c<='Z') return c-'A';
    return 26;
}
int hash(const char *s) {
    enum { N=26 };
    static const int p[N+1]={
        3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,
        3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,
        1
    };
    int h=1; for(;*s;s++) h*=p[code(*s)];
    return h;
}

Здравствуйте, Artem Korneev, Вы писали:

AK>·>А как насчёт: отсортировать массив, используя в качестве компаратора сравнение строк, в которых символы предварительно сортируются.

AK>Дополнительная сортировка массива ухудшает параметры этого алгоритма. Там итоговое быстродействие будет умножено на log(n), где n — кол-во строк. Ибо сортировка всяко медленнее, чем простой одноразовый проход по списку строк.
AK>Ничего лучше, чем просто проход по всем строкам и раскидывание строк по словарю, где ключом будет хэш отростированной строки, там уже не придумаешь. Проблема только в скорости генерации этого хэша. Для сортировки строки мы имеем m * log (m), где m — кол-во символов в строке.
Ну хеш это первое очевидное решение. Просто по идее нужна хитрая структура HashMap<String, List<String>> которая может быть большой в памяти. И в итоге эффективность может быть хуже (хотя бы за счёт большей нагрузки на менеджер памяти и фрагментации). Поэтому просто in-place отсортировать массив c хитрым компаратором может оказаться гораздо эффективнее. Тут только конкретные тесты могут помочь с выбором.

AK>Сейчас взбрёл мне в голову мысль, что вот для сортировки строки мы можем использовать какой-нибудь bucket sort, дающий линейное время сортировки, но пригодный только для небольшого количества элементов. Вот наверное это-то и имелось в виду. Хм..
хорошая мысля.

Здравствуйте, Artem Korneev, Вы писали:

AK>Получил недавно любопытное задание на интервью. Вот текст задания:

AK>

Anagrams are defined as words with the same length and same number of characters in any order.
AK>Eg:
AK>bat/tab/abt are anagrams
AK>aabb/baba/bbaa/abab — anagrams
AK>abcd/abce — are not anagrams (different characters)
AK>aaab, aabb — are not anagrams (different character count)

AK>Given a list of words — { abcd, bbb, abc, bat, cat, yyyyxxxx, tab, atb, rat, cab, xxyyxxyyxx, atb }
AK>Print out the anagram pairs — {{abc, cab}, {bat, tab, atb, atb}}

AK>Assuming that the input is of type [a-z], can you optimize the solution.

AK>С анаграммами всё просто — они легко находятся, если сравнивать отсортированные копии строк. А вот с оптимизацией я так и не разобрался. Я так понимаю, смысл там в генерации уникального хэша для каждой строки, но как сделать хэш одинаковым для разных строк, содержащих тот же набор букв, я пока не понял.

А хэш реально нужен? Может быть, просто отсортировать список строк, используя в качестве предиката сравнение отсортированных строк-элементов?

Здравствуйте, Artem Korneev, Вы писали:

AK>Подскажите, какой тут был бы правильный алгоритм? И, что более интересно — подскажите, какие ещё полезные способы хэширования стоит посмотреть чтобы лучше понимать эту тему?

А есть условия задачи? Максимальное число повторяющихся символов? Длина строк?

С хеш-таблицей решение очевидно. Если нужно гарантированное n*log(n) в худшем случае (и n по памяти), то можно сделать ключом вектор счётчиков символов строки и сортировать по нему.