0

私は Dijkstra による EWD 316 を読んでいて、例に行き詰まりました。53 ページで、Dijkstra は次のように定義しています。

異なる隣接する空でないサブシーケンスのペアのみを含む、1、2、および 3 で構成されるシーケンスを考えてみましょう。

彼はそのようなシーケンスを良いと呼んでいます。問題は、長さ 100 の適切なシーケンスが少なくとも 1 つあるという事実を考慮して、長さ 100 の最初のシーケンスを含むすべての適切なシーケンスをアルファベット順にリストすることです。

まず、ダイクストラが言う「サブシーケンス」とは「部分文字列」のことだと思いますが（ウィキペディアの定義を参考にしています）、これは本質的な問題ではありません。私が見る限り、シーケンスが適切な場合、シーケンス内の 1、2、および 3 を並べ替えると、別の適切なシーケンスが生成されるという意味で、定義は対称的です。定義が特定の数値に言及していないためです。ただし、Dijkstra は最初のいくつかの適切なシーケンスを (アルファベット順に) 示しており、たとえば、12 がリストに含まれていても、シーケンス 21、13、23、31、および 32 は含まれていません。また、彼のアルゴリズムは試行シーケンスの最後の 3 を削除します。

些細なことを見逃していると確信していますが、何がわからないのですか。また、私は英語のネイティブスピーカーではないので、完全に形式的/数学的な表記法で優れているという特性を表現していただければ幸いです.

ps: 適切な既存のタグが見つかりませんでした。

4

1 に答える 1

0 
 contain only pairs of different adjoining non-empty subsequences

隣り合う 2 つの部分文字列が異なることを意味します。私の推測では、あなたが推測したように、adjoiningはペアを指しますが、彼は部分文字列の代わりにsubsequencesという単語を使用しています- 彼は間違いなく部分文字列を意味し、そうでなければ良くありません.3212321

したがって、アルファベット順に開始します。

1でいい、1で伸ばす

11 は良くありません。末尾の 3 を削除し (この場合はありません)、最後の桁を 1 増やします

12 良い

121 良い

1211 良くない

1212 良くない

1213 良い

...

さて、このリストに21(および13, 23, 31...) はありますか? 21明らかに「良い」シーケンスです。しかし、21はアルファベット順で で始まる文字列の後1にあるため、 で始まる適切な文字列が無数にある場合、1実際には に到達することはありません21。

もっと単純な問題を想像してみてください: すべての自然数をアルファベット順に並べてください。

1
11
111
...

に到達することはありません2。これは、それが自然数の集合にないという意味ではなく、アルファベット順のリストの有限位置にないというだけです。

于 2013-11-05T16:04:14.063 に答える