Можно ли сгенерировать Pangram из заданного списка слов?

Question

Панграмма - это предложение, использующее каждую букву алфавита хотя бы один раз.

Можно ли сгенерировать самую короткую Панграмму из данного списка слов?

Допустим, у меня есть список слов, как это

cat monkey temp banana christmas 
fast quick quickest jumping 
white brown black blue
fox xor jump jumps oven over 
now the is was 
lazy laziest crazy
dig dog joker mighty

И, как для создания списка возможных панограмм, как следующие

the quick over lazy jumps fox dog brown
brown dog fox jumps lazy over quick the
quick brown fox jumps over the lazy dog

Грамматику и порядок слов пока не нужно рассматривать (я собираюсь сделать это не на английском языке)

Любые идеи, алгоритмы, коды, ссылки, будут с благодарностью!

PS: это не домашняя работа

Answer 1

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

Более эффективный метод, вероятно, состоит в том, чтобы пройтись по каждому слову и установить массив bools (или набор битов, например, в 32-битном int) вместе с длиной слова. Затем вы можете найти биты, которые вместе производят значение со всеми установленными 26 битами, и у вас есть панграмма.

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

Если вы хотите получить еще более изощренные знания об этом, вы можете начать с создания набора битов того же типа, что и выше. Затем возьмите их и сложите вместе биты, чтобы определить, какие буквы встречаются в наименьшем количестве слов. Когда вы начинаете генерировать потенциальную панграмму, вы знаете, что она должна включать одно из этих слов. Например, в приведенном выше списке "ленивый", "ленивый" и "сумасшедший" кажутся единственными, которые включают "z", так что вы сразу знаете, что каждая панграмма должна включать одно из этих трех слов. Ни одно из них не включает "q", и единственные слова, которые включают "q", кажутся "быстрыми" и "самыми быстрыми", поэтому (опять же) каждая панграмма должна включать одно из этих двух (конечно, я собираюсь от ручного осмотра здесь, так что я мог пропустить ни слова). Таким образом, каждая возможная панграмма из этого списка включает (и может начинаться с): (быстрая | быстрая) (ленивая | ленивая | сумасшедшая).

Вы также можете рассмотреть возможность предварительной обработки списка слов: любое слово, которое длиннее другого, но не содержит хотя бы одной буквы, отсутствующей в другой, может быть немедленно удалено. В качестве гипотетического примера, если у вас есть "ab" и "abab", вы знаете, что "abab" никогда не может привести к более короткой панграмме, чем "ab", поэтому вы могли бы также немедленно исключить ее из списка.

Answer 2

Конечно. Вот один алгоритм:

1. Пусть L_w будет заданным списком слов.
2. Пусть L_d будет списком различных слов в L_w.
3. Пусть L_c будет списком всех возможных комбинаций с использованием слов из L_d. Если L_d содержит n элементов, L_c будет содержать 2ⁿ элементов.
4. Пусть P будет самой короткой панграммой (желаемый результат). Изначально P будет пустым.
5. Итерировать по каждому элементу (комбинации) в L_c. В каждой итерации:
   1. Пусть C будет текущей рассматриваемой комбинацией.
   2. Проверьте, является ли C панграммой.
      1. Если C является панграммой, проверьте, является ли P пустым или C короче, чем P.
         1. Если P пусто или если C короче P, пусть P будет C

Answer 3

Идеи для поиска приближенных решений:

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

Оценка слов может выглядеть примерно так:

score = 0
foreach unique letter in word
  score += 1/letter_frequency[letter]
score /= word.length