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

Question

Анаграмма:

Анаграмма - это тип игры слов, результат перестановки букв слова или фразы для получения нового слова или фразы, используя все оригинальные буквы ровно один раз;

Проблема суммы подмножеств:

Проблема заключается в следующем: существует ли непустое подмножество с заданным набором целых чисел, сумма которого равна нулю?

Например, если задано множество {−7, −3, −2, 5, 8}, ответ положительный, потому что подмножество {−3, −2, 5} суммируется с нулем.Проблема в NP-полноте.

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

Я ошибаюсь?

Answer 1

Две проблемы похожи, но не изоморфны .

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

Answer 2

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

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

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

Answer 3

Я думаю, что вы не правы.

Генерация анаграммы должна быть проще, чем сумма подмножеств, потому что я могу придумать тривиальный алгоритм 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 set), но анаграмма всегда должна иметь ту же длину, что и входное слово.

Answer 4

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

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