Возможно ли создать Pangram из данного списка слов?

Question

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

Возможно ли создать кратчайший Pangram из списка слов?

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

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 

и, как генерировать список возможного pangrams как следующее

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 для каждой буквы, которая находится в строке. В конце концов, это pangram, если у bools установлено значение true.

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

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

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

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

Answer 2

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

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

Word scoring может выглядеть примерно так:

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

Answer 3

Несомненно. Вот один алгоритм:

1. Пусть L _ж быть список слов данных.
2. Пусть л _д быть список различных слов в L _ш.
3. Пусть л _с быть список всех возможных комбинаций с использованием слов из L _д. Если L _д содержит п элементы, L _с будет содержать 2 ^п элементы.
4. P be кратчайший Pangram (желаемый результат). Первоначально P будет пустым.
5. Итерации по каждому элементу (комбинации) в L _c. На каждой итерации:
   1. C Рассматривается текущая комбинация.
   2. Проверьте, есть ли C является Pangram.
      1. Если C является панграмма, проверьте P пуст или если C короче P.
         1. Если P пуста или если C короче P, пусть P быть C