長さ n のリンドン語を生成する Python プログラム

この質問では、英数字の配列を使用してリンドンのすべての単語を検索します。

始める前に、まずリンドンという言葉の定義を理解しましょう。

• すべての単語はリンドン語であり、厳密に辞書順にすべてのサイクルよりも小さくなります。

以下はリンドンの言葉の例です。

• ab - "ab" は、そのすべての順列 "ba" よりも辞書編集的に厳密に小さいです。

• 89 - 「89」のローテーションは「98」であり、厳密には辞書編集上「89」より大きくなります。

• abc - 「abc」の回転は「bca」と「cab」であり、厳密には「abc」よりも大きくなります。

以下はリンドン語以外の単語の例です。

• aaa - 「aaa」の回転はすべて同じであるため、aaa は非リンデン語です。

• bca - 「abc」はそれより回転が小さいため、「bca」は非リンデン語です。

問題文

- 英数字を含む長さ K の文字配列が与えられています。さらに、正の整数を含む n が与えられます。タスクは、配列で指定された英数字を使用して、長さ n のリンドン語をすべて見つける必要があることです。 ＃＃＃例＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明

- 配列文字を使用して、長さ 3 のすべての Lydon 単語を生成します。

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明 - 「01」は、0 と 1 を使用して形成できる唯一の Lyndon 単語です。

＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

説明- a、c、d 文字を使用して長さ 2 のリンドン語を生成します。

方法1 デュバルのアルゴリズムと呼ばれる、リンデン語を生成する特別なアルゴリズムがあります。

＃＃＃アルゴリズム＃＃＃

ステップ 1 - リンドン語の長さを表す「n」値と、リンドン語の作成時に使用する文字を含む chars 配列を定義します。

ステップ 2- リストを並べ替えます。

ステップ 3 - 「インデックス」リストを -1 で初期化します。

ステップ 4- インデックス リストが空でなくなるまで繰り返します。

ステップ 5 - 「インデックス」リストの最後の要素を 1 増やします。

ステップ 6- list_size が n に等しい場合、リストの値を出力します。

ステップ 7

- 長さが n になるようにインデックスをリストに追加します。

ステップ 8

- リストの最後の要素が配列の最後のインデックスと等しい場合は、リストから削除します。 ＃＃＃例＃＃＃ 入力例を使って例を理解しましょう。

並べ替えられたリストは ['a', 'c', 'd'] になります。

インデックス リストは、最初の反復で [-1] から [0] に更新されます。その後、インデックスの長さは 2 になり、[0, 0] になります。

2 回目の反復では、リストが [0, 1] に更新され、最初の Lyndon 単語「ac」が見つかります。

3 回目の反復では、リストは [0, 2] になり、2 番目の Lyndon 単語は「ad」になります。また、最後の要素は array_len -1 に等しいため、リストから削除されます。

4 回目の反復では、リストは [1] になります。 [1,1]は後日更新します。

次の反復では、リストは [1, 2] になり、3 番目の Lyndon ワー「cd」が見つかります。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- O(nlogn)。最初に「文字」リストをソートする必要があるためです。

空間複雑度

- リストに n 個のインデックスを格納するため、O(n) になります。

• Duval アルゴリズムは、長さ n のリンドン語を生成する最も効率的な方法です。ただし、配列文字のみを使用するようにメソッドをカスタマイズしました。

以上が長さ n のリンドン語を生成する Python プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。