4

パングラムは、アルファベットのすべての文字を少なくとも 1 回使用する文です。

与えられた単語リストから最短のパングラムを生成することは可能ですか?

たとえば、このような単語リストがあるとしましょう

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: これは宿題ではありません

4

3 に答える 3

3

もちろん。1 つのアルゴリズムを次に示します。

  1. 与えられた単語のリストをL wとする。
  2. L dをL w内の異なる単語のリストとする。
  3. L cを、 L dからの単語を使用したすべての可能な組み合わせのリストとします。L dにn 個の要素が含まれる場合、L cには 2 n 個の要素が含まれます。
  4. Pを最短のパングラム (望ましい結果) とする。最初はPは空です。
  5. L cの各項目 (組み合わせ) を反復処理します。各反復で:
    1. 現在検討中の組み合わせをCとします。
    2. Cが Pangram かどうかを確認します。
      1. Cがパングラムの場合、Pが空であるか、またはCがPよりも短いかどうかを確認します。
        1. Pが空の場合、またはCがPよりも短い場合、PをCとする
于 2009-12-09T16:11:06.703 に答える
3

単語リストから考えられるすべてのパングラムを生成する最も簡単な方法は、リストから考えられるすべての単語の組み合わせを生成し、それぞれについて、それがパングラムかどうかを確認することです。チェックを行うには、文字列を調べて、文字列内の各文字の bool を true に設定します。最後に、bools がすべて true に設定されている場合はパングラムです。

より効率的な方法は、おそらく各単語を調べて、単語の長さと一緒に bool の配列 (または 32 ビット int などのビットのセット) を設定することです。次に、26 ビットすべてが設定された値を生成する OR 演算されたビットを見つけることができ、パングラムが得られます。

パングラムをまとめるときに、境界チェックを追加できます。単語を追加すると潜在的なパングラムが現在の最短のパングラム (存在する場合) よりも長くなる場合は、そのチェックをその場で停止します。単語を長さで並べ替えることから始めた場合、より長い組み合わせを見つけた瞬間に、その一連の試行をすべてやめて、次の可能性に進むことができます。

さらに高度にしたい場合は、上記と同じ種類のビット セットを作成することから始めることができます。次に、それらを取得し、ビットを合計して、最も少ない単語にどの文字が出現するかを判断します。潜在的なパングラムを生成し始めると、それらの単語のいずれかが含まれている必要があることがわかります。たとえば、上記のリストでは、「lazy」、「laziest」、および「crazy」だけが「z」を含むように見えるため、すべてのパングラムが必要であることがすぐにわかりますこれらの 3 つの単語のいずれかを含めます。それらのどれにも「q」は含まれておらず、「q」を含む唯一の単語は「速い」と「最も速い」であるように思われるため、（再び）すべてのパングラムにはこれら2つのうちの1つが含まれている必要があります（もちろん私は行きますここでは手作業で検査しているため、単語を見逃している可能性があります)。したがって、そのリストのすべての可能なパングラムには、(そして、最初から始めることもできます): (quick|quickest) (lazy|laziest|crazy) が含まれます。

単語リストの前処理を検討することもできます。他の単語より長いが、他の単語から欠落している文字が少なくとも 1 つ含まれていない単語は、すぐに削除できます。仮定の例として、"ab" と "abab" がある場合、"abab" が "ab" よりも短いパングラムになることは決してないことがわかっているので、すぐにリストから削除することもできます。

于 2009-12-09T16:11:06.567 に答える
2

おおよその解を見つけるためのアイデア:

  1. セットの文字頻度を決定する
  2. 各単語を採点する
  3. すべての文字が得られるまで、スコアが最も高い単語を追加します

単語スコアリングは次のようになります。

score = 0
foreach unique letter in word
  score += 1/letter_frequency[letter]
score /= word.length
于 2009-12-09T16:09:48.160 に答える