Генерация анаграммы - разве это не сумма подмножества?

Если бы вы доказали, что решение нахождения анаграммы (не более полиномиального числа раз) решает проблему суммы подмножеств - это было бы революцией в информатике (вы бы доказали, что P = NP).

Ясно, что поиск анаграмм - это проблема полиномиального времени:

Проверить, являются ли две записи анаграммами друг друга, так же просто, как отсортировать буквы и сравнить полученные строки (то есть C*s*log(s) время, где s - количество букв в записи). У вас будет максимум n таких проверок, где n - количество записей в словаре. Таким образом, очевидно, что время работы ~ C*s*log(s)*n ограничено полиномом размера ввода - вашей входной записи и словаря вместе взятых.

ИЗМЕНИТЬ:

Все вышеизложенное справедливо только в том случае, если задача поиска анаграммы определяется как поиск анаграммы входной фразы в словаре возможных полных фраз.

В то время как формулировка проблемы поиска анаграммы в исходном вопросе выше...

Теперь скажем, что у нас есть словарь из n слов. Теперь проблема генерации анаграммы может быть сформулирована как поиск набора слов в словаре (из n слов), которые используют все буквы ввода.

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

Однако это сразу же кажется проблематичным и неясным, потому что (1) обычно фраза представляет собой не просто последовательность случайных слов (она должна иметь смысл как целая фраза), (2) обычно слова во фразе требуют разделителей, которые также являются символами, поэтому это не так. снимите флажок, если во входных данных требуются разделители (пробелы), чтобы разрешить отдельные записи в словаре, и если разделители разрешены в одной словарной записи.

Итак, в моем первоначальном ответе выше я применил семантическую бритву, интерпретируя определение проблемы единственным способом, которым оно является недвусмысленным и имеет смысл как нахождение анаграммы.

Но также мы можем интерпретировать определение авторов следующим образом:

Учитывая словарь из n последовательностей букв (отдельные статьи словаря могут содержать одинаковые последовательности) и одну целевую последовательность букв, найдите любое подмножество записей словаря, которое при объединении вместе будет точной перестановкой целевой последовательности букв ИЛИ определить, что такого подмножества не существует.

^^^- Несмотря на то, что эта задача больше не имеет смысла как проблема поиска анаграмм, она все же интересна. Это совсем другая проблема, чем то, что я рассмотрел выше.

Остается непонятным еще один момент - гибкость алфавита. Для конкретности в постановке задачи также должно быть указано, является ли набор букв фиксированным ИЛИ допускается его переопределение для каждого нового решения задачи при указании словаря и целевой последовательности указанных букв. Это важно - от этого зависят возможности и сложность.

Вариант этой задачи с возможностью определения алфавита (доступного количества букв) для каждого решения в отдельности фактически эквивалентен задаче о сумме подмножеств. Это делает его NP-полным.

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

Учитывая набор (мультимножество) натуральных чисел (допускаются повторяющиеся числа) и целевое натуральное число, найдите любой поднабор, сумма которого точно равна целевому числу, ИЛИ определите, что такой поднабор не существует.

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

Этот только положительный вариант суммы подмножества эквивалентен варианту суммы подмножества с нулевой суммой, данному автором (см., например, Статья в Википедии о сумме подмножества).

Эти две задачи похожи, но не являются изоморфными.

• В анаграмме порядок букв имеет значение. В сумме подмножества порядок не имеет значения.
• В анаграмме должны использоваться все буквы. В сумме подмножества подойдет любое подмножество.
• В анаграмме подгруппы должны образовывать слова, взятые из сравнительно небольшого словаря допустимых слов (словаря). В сумме подмножества группы не ограничены (нет словаря допустимых группировок).

Я думаю, вы ошибаетесь.

Генерация анаграммы должна быть проще, чем сумма подмножества, потому что я могу разработать тривиальный алгоритм O (n) для ее решения (как определено):

initialize the list of anagrams to an empty list
iterate the dictionary word by word
    if all the input letters are used in the ith word
        add the word to the list of anagrams

return the list of anagrams

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

Это не NP-Complete, потому что при наличии одного набора букв набор анаграмм остается идентичным независимо от того.

Всегда существует единственное отображение, которое преобразует буквы ввода L в набор анаграмм A. Таким образом, мы можем сказать, что f(L) = A для любого выполнения f. Я считаю, если я правильно понимаю, что это делает функцию детерминированной. Порядок набора не имеет значения, поэтому рассмотрение недетерминированного решения с другим порядком недопустимо, оно также недопустимо, потому что все записи в словаре уникальны и, следовательно, могут быть детерминистически упорядочены.