6

リストを回転させる機能があります：

rotate :: [a] -> [a]
rotate [] = []
rotate (x:xs) = xs ++ [x]

ここで、有限リストの可能なすべてのローテーションでリストを提供する関数が必要です。

rotateAll :: [a] -> [[a]]

命令型言語では、（疑似コードで）次のようにします

for i = 1 to length of list
  append list to rotateList
  list = rotate(list)

もちろん、命令的に考えても、この問題の機能的な解決策を見つけるのにはおそらく役立ちません。これに対処する方法についてのヒントを探しています。

追加の考え:

これを解決するには、2 つの問題に取り組む必要があります。最初に、リストを繰り返しローテーションし、各結果をリストに収集する必要があります。したがって、最初の解決策は次のようなことをする必要があります

rotateAll xs = [xs (rotate xs) (rotate (rotate xs)) (rotate (rotate (rotate xs))) ...]

もちろん、これを何回行うかはわかりません。take (length xs)これを無限に実行してから、必要な有限数のリストを取得するために使用することに満足します。これは実際に 2 番目の問題、つまりいつ停止するかを決定することを示しています。takeを使用することが問題を解決するための最も効率的またはエレガントな方法であるかどうかはわかりませんが、これを入力しているときに頭に浮かび、動作するはずです。

補遺: 2 つの解決策を自分で、またはヒントで見つけました。より高速な、または異なるアプローチを使用する他のソリューションを喜んで歓迎します。ありがとう！

4

11 に答える 11

8

であらかじめ定義された関数を使用してくださいData.List。4 つの関数呼び出し、再帰なし、rotate関数なしを使用して、すべての回転のリストを取得できます。

ここに完全な解決策を掲載しないように依頼しました。それを見たい人のために、完全な解決策 (1 行のコード) がhttp://pastebin.com/atGiw1igに表示されます。

于 2012-08-08T22:00:37.850 に答える
3

iterateとは別に、n 回転のリストを生成する関数を作成できます。ケース n=0 は入力をリストにラップするだけで、ケース n=m+1 はケース m の結果に入力を追加します。標準関数を使用することが一般的に好まれますが、独自のソリューションを作成することが健全な場合もあります。

于 2012-08-08T18:28:12.540 に答える
2

このサイトを検討することもできます。同じ質問に答える回転関数を定義する方法。

コメントによる編集:に基づく実装とに基づく実装rotateは、リストの長さが 2 次でなければなりませんinits。ただし、 andtailsに基づくものは、いくつかの二次トラバーサルを実行するため、効率が低下するはずです。ただし、これらのステートメントは、結果を完全に評価した場合にのみ有効であることに注意してください。さらに、コンパイラはコードを改善できる可能性があるため、これらのステートメントは注意して扱う必要があります。initstails

于 2012-08-08T18:35:10.607 に答える
1

私は2つの解決策を思いつきました。1つ目は、質問を投稿した後に私に届いた手作りのものです。

rotateAll :: [a] -> [[a]]
rotateAll xs = rotateAll' xs (length xs)
    where rotateAll' xs 1 = [xs]
          rotateAll' xs n = xs : rotateAll' (rotate xs) (n - 1)

もう1つは@Tiloの提案を使用しています：

rotateAll :: [a] -> [[a]]
rotateAll xs = take (length xs) (iterate rotate xs)
于 2012-08-08T18:29:43.827 に答える
1

補遺: 2 つの解決策を自分で、またはヒントで見つけました。より高速な、または異なるアプローチを使用する他のソリューションを喜んで歓迎します。ありがとう！

他に指摘されていないのでcycle、有限リストにこのソリューションを追加すると思いました:

rotations x = let n = length x in map (take n) $ take n (tails (cycle x))

無限リストxの場合、回転はtails x.

を評価するcycle xと、時間と空間は O(n) であり、 の各要素tailsは O(1) であり、take n時間と空間は O(n) ですが、この 2 つtake nは入れ子になっているため、結果全体を評価すると時間と空間は O(n^2) になります。

次のローテーションを遅延生成する前に各ローテーションをガベージ コレクションする場合、スペースは理論的には O(n) になります。

あなたが消費している量について賢いなら、必要はなく、単にorをmap (take n)歩き、スペース O(n) を保つことができます。cycle xtake n (tails (cycle x))

于 2012-08-09T07:59:45.367 に答える
1

それらを再帰的に生成することもできます。空または単一の要素リストのすべての回転を生成するのは簡単で、 の回転を生成するには、のすべての回転の正しい位置にx:xsを挿入するだけです。xxs

これを行うには、挿入するインデックスを生成し (単純にリスト [1, 2, ...] の前の回転がこの順序であると仮定) 、正しい位置zipWithに挿入するために使用します。x

または、とを組み合わせて使用split​​して位置を中心に回転させて、それらを再び接着することもできます。initstailszipWith

于 2012-08-08T18:38:12.807 に答える