Расчет индекса анаграммы

Для заданной входной строки длиной до 25 символов, состоящей из символов A-Z, выведите ее индекс в отсортированном по алфавиту списке всех возможных анаграмм входной строки. Входная строка не чувствительна к регистру. Вводимые символы могут повторяться. Приложение должно завершиться менее чем за 500 мс и занять менее 1 ГБ памяти.

На первый взгляд кажется, что это невозможно сделать без произвольной математической библиотеки точности. В худшем случае ввод состоит из 25 уникальных символов, в результате получается 25! возможные анаграммы. 25! на порядки больше, чем 2 ^ 64. Поскольку связь между индексами и строками не является прямой и должна быть вычислена, нет способа просто преобразовать строку в число.

Это исходит из интервью, которое я получил на днях. Я не мог придумать для них решения, и они настаивали на том, что действительно есть хорошее решение...


algorithm math combinatorics anagram
person Community    schedule 05.09.2013    source источник
comment
Это не дубликат, потому что вопрос, который я действительно задаю здесь, заключается в том, как это сделать без использования произвольной математической библиотеки точности.   -  person    schedule 12.09.2013
comment
И очевидный ответ: это невозможно, потому что ответ может быть больше 2^64.   -  person Chronial    schedule 13.09.2013

Ответы (1)


arrow_upward
7
arrow_downward

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

Используя этот факт, вы можете получить индекс любой анаграммы, подсчитав количество анаграмм для префиксов, предшествующих ей в алфавитном порядке. Например, возьмем MISSISSIPPI: частоты букв I: 4, M: 1, P: 2, S: 4, всего 11!/(4!1!2!4!) = 34650 анаграмм.

  • Количество анаграмм, начинающихся с I, равно 10!/(3!1!2!4!) = 12600.
  • Количество анаграмм, начинающихся с MII, равно 8!/(2!0!2!4!) = 420.
  • Количество анаграмм, начинающихся с MIP, равно 8!/(3!0!1!4!) = 280.
  • Количество анаграмм, начинающихся с MISI, равно 7!/(2!0!2!3!) = 210.
  • Количество анаграмм, начинающихся с MISP, равно 7!/(3!0!1!3!) = 140.
  • Количество анаграмм, начинающихся с MISSII, равно 5!/(1!0!2!2!) = 30.
  • Количество анаграмм, начинающихся с MISSIP, равно 5!/(2!0!1!2!) = 30.
  • и так далее...

Суммируйте эти числа, и вы получите индекс. Но да, вам, вероятно, понадобится какая-то библиотека чисел произвольной точности, потому что, как вы говорите, в худшем случае их 25! анаграммы и индекс могут выходить за пределы для 64-битных целых чисел.

Это не кажется очень элегантным, хотя, если есть лучшее решение, я хотел бы услышать об этом.

person Joni    schedule 05.09.2013
comment
Я думаю, что это выглядит довольно элегантно. Я предполагаю, что это то, что искал спрашивающий - единственное, что отсутствует, - это библиотека bignum или ваша собственная реализация такой. Это все еще должно длиться меньше половины секунды, и вы решили суть проблемы — сделайте это, не создавая все анаграммы. - person vroomfondel; 06.09.2013
comment
Я согласен, что это элегантное решение. Если вы уменьшите дроби и повторно используете результаты вычислений, это также должно быть примерно таким же быстрым, как вычисление x! для некоторого x с x! ≈ index, что, как я полагаю, является минимально необходимым вычислением. - person Chronial; 06.09.2013