5

最近問題に挑戦しています。そして、この場合、私はほとんど問題を抱えていません。

Input: generatingListforRightShifting 2 [1,2,3,4,5,6,7,8]
Output: [[1,2,3,4,5,6,7,8],[8,1,2,3,4,5,6,7],[7,8,1,2,3,4,5,6]]

ご存じのとおり、このプログラムは要素を正しい方向にシフトします。第 1 引数は、シフトを行う回数を示します。初心者として、よく知られているいくつかのリスト関数を解決しようとしています。そして再帰を使用します。しかし、私には再帰のアイデアが明確ではありません。私のコードは次のとおりです。

generatingListforRightShifting' _ []=[]
generatingListforRightShifting' 0 x=x
generatingListforRightShifting' n xs=   newList where
                        newList=takeWhile(\i->[1..n] 
                                            <=n)(reverse(take 
                                           i(reverse xs))++reverse(drop i(reverse xs)))

私がしている主な間違いは、takeWhile の部分にあることを理解しています。しかし、どうすればn回繰り返すことができますか。Input:generatingListforRightShifting 2 [1,2,3,4,5,6,7,8] Output: [7,8,1,2,3,4, 5,6] しかし、以前のシフトをすべて取得しようとすると、できません。

誰でもここで私を助けてくれますか。また、解決策を教えていただければ幸いです。

4

6 に答える 6

3

これは、シフトではなく回転としてより一般的に知られています。最後の要素と、最後の.

rotateOnce lst = (last lst):(init lst)

また、2 回回転することは、rotateOnce を 2 回呼び出すことと同じであることに注意してください。したがって、メソッドは前の結果からの再帰として単純に実装できます。

rotateN 0 lst = [lst]
rotateN n lst = lst : rotateN (n-1) ((last lst):(init lst))

(注: これは最適な解決策ではない可能性があります。)

于 2012-10-24T11:57:19.767 に答える
2

「シフト」を再帰的に定義できます:shift 0はノーオペレーション、shift 1+n (x:xs)isshift n xsです。

何かのようなもの：

shift 0 = \x -> x
shift n = \lst@(x:xs) -> (shift (n-1) xs)

-- example:
sh3 = shift 3

次に、「回転」の問題が簡単になります。

rotate n = \lst -> (shift lst) ++ (take n lst)
于 2012-10-24T11:53:45.260 に答える
2

あなたは、最初からやり直すよりもコードを修正することを好むようです。それでは、あなたのコードを見てみましょう。まず、メインリストのチョッピング:

reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs))

reverse (take i (reverse xs))リストの最後から要素を取得するようになりましiたが、これを実現するにはリストを 2 回逆にします drop (length xs - i) xs。reverse (drop i (reverse xs))) 同様に、として実装できますtake (length xs - i) xs。それは私たちに与えます

drop (length xs - i) xs ++ take (length xs - i) xs

リストを\i->[1..n]<=nと比較するため、コードは意味をなしません。これは機能しません。からまで実行さ れるループを作成しようとしていると思いますが、これは良い計画です。リスト内包表記を使用して、必要なものを取得しましょう。[1..n]ni1n

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1 .. length xs], i <= n]

しかし、今は 1 からリストの長さまで実行していますが、上記の数字を捨てていますn。

[drop (length xs - i) xs ++ take (length xs - i) xs | i <- [1..n]]

これはnを超えることがlength xsできますが、そこに大きな問題は見られません。最初に確認できます。

ここで を使用 iしているだけ(length xs - i)で、実際には length xs必要以上に多くの再計算を行っていることにi注意し1てください。nlength xs - ij=length xs -ijlength xslength xs - n

[drop j xs ++ take j xs | j <- [length xs,length xs - 1 .. length xs - n]]

たとえば、これは機能します[6,5..1] == [6,5,4,3,2,1]

した方がきれいでしょう

let l = length xs in
  [drop j xs ++ take j xs | j <- [l,l - 1 .. l - n]]

またはtake、算術よりも算数が好きな場合は、次を使用できます。

let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 .. 0]]

これには、やりすぎを防ぎ、最初に戻ったときに停止するという追加の利点があります。

関数の名前をからgeneratingListforRightShiftingに変更します。rotationsR

rotationsR n xs = let l = length xs in
  take n [drop j xs ++ take j xs | j <- [l,l - 1 ..]]

これは を与えrotationsR 6 [1..4] == [[1,2,3,4],[4,1,2,3],[3,4,1,2],[2,3,4,1],[1,2,3,4]]ます。

左回転はより簡単に見えます:

rotationsL n xs = take n [drop j xs ++ take j xs | j <- [0..length xs]]

余談: 私は自分自身を助けることができませんでした, 申し訳ありません, そして、私は再び始めました.

私はまだ、そのすべてを毎回落としたり取ったりするのは好きではありません。私はむしろ無限に多くのコピーを並べてxs(最初のN：cycle xstails

rotationsL' n xs = let l = 長さ xs in テイク n . マップ (テイク l) . 尾。サイクル $ xs

遅延評価のため、これまでに限られた量しかcycle xs計算されませんが、これは実行して実行できrotationsL' 10 [1..4]ます:

 [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4],[2,3,4,1]]

そのように適切なローテーションを行うのも良いでしょうが、無限リストの最後から開始して戻る必要があるため、うまくいきません。ただし、リバースを再利用して、必要なものを取り、リバース トリックをもう一度使用しましょう。

rotationsR' n xs = let l = length xs in
  take n . map (reverse.take l) . tails . cycle . reverse $ xs

余談: 元のコードにもっと厳密に固執したい場合は、次のことができます。

generatingListforRightShifting n xs = 
    [reverse (take i (reverse xs)) ++ reverse (drop i (reverse xs)) | i <- [1..n]]
于 2012-10-24T16:44:08.927 に答える
1

I find a left rotation to be very straight forward using splitAt:

import Data.Tuple (swap)
rotateLeft n = uncurry (++) . swap . splitAt n

> rotateLeft 2 "Hello World!"
>>> "llo World!He"
于 2012-10-24T18:05:10.303 に答える
1

非常に複雑な現在のアプローチはやめます。代わりに、操作のさまざまなコンポーネントを抽象化することに集中してください。操作を部分に分割すると、リストを左に回転するコンポーネントと、リストを右に回転するコンポーネントの 2 つの対称コンポーネントがあることがわかります。定義したい操作は、いくつかのリストで指定された回数だけ右ローテーションを繰り返します。これは、左または右の回転の指定された回数の繰り返しを取ることによって、目的の操作を定義できることを示唆しています。例えば、

left :: [a] -> [a]
left [] = []
left xs = tail xs ++ [head xs]

right :: [a] -> [a]
right [] = []
right xs = last xs : init xs

shiftL :: Int -> [a] -> [[a]]
shiftL n = take n . iterate left

shiftR :: Int -> [a] -> [[a]]
shiftR n = take n . iterate right
于 2012-10-24T12:29:20.560 に答える
1

ここでの使用cycleはいいようです：

shifts n xs = take (n+1) $ shifts' (cycle xs)
  where
    len = length xs
    shifts' ys = take len ys:shifts' (drop (len-1) ys)
于 2012-10-24T13:15:12.110 に答える