Generowanie listy utworzonej przez prawe elementy zmieniające n razy

Question

Próbuję ostatnio rozwiązać problem. I w tym przypadku mam kilka problemów.

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]] 

Jak rozumiesz ten program przesunie element we właściwym kierunku. Pierwszy argument wskazuje, ile razy będzie się przesuwać. Jako początkujący próbuję rozwiązać kilka dobrze znanych funkcji listy. i używając rekursji. Ale dla mnie idea rekursji nie jest jasna. Mój kod to:

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))) 

Rozumiem, że głównym błędem, który robię, jest część czasu. Ale jak mogę iterować przez n razy. Zrobiłem już program, który bezpośrednio pokazuje przesunięty wynik, taki jak Wejście: generateListforRightShifting 2 [1,2,3,4,5,6,7,8] Wyjście: [7, 8, 1, 2, 3, 4,5,6] Ale kiedy próbuję uzyskać wszystkie poprzednie zmiany, nie mogę.

Czy ktoś może mi pomóc tutaj. Witam cię również, jeśli podasz mi pomysł rozwiązania.

Answer 1

Możesz zdefiniować "przesunięcie" rekursywnie: shift 0 jest trybem dowolnym, shift 1+n (x:xs) jest shift n xs.

Coś jak:

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

-- example: 
sh3 = shift 3   

Następnie 'rotate' problemem staje się łatwiejsze:

rotate n = \lst -> (shift lst) ++ (take n lst) 

Answer 2

To jest bardziej znany jako obracanie zamiast przesuwania. Obracanie listy raz w prawo jest proste, ponieważ istnieją metody, aby uzyskać last element i sublist of all elements but the last.

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

Należy również pamiętać, że obracanie dwa razy jest równoważne dwukrotnemu wywołaniu obrócenia. Dlatego sposób mogą być realizowane po prostu jako rekursji z poprzedniego związku:

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

(. Uwaga: to nie może być najbardziej optymalnym rozwiązaniem)

Answer 3

chciałbym spaść obecnego podejścia, które jest bardzo zwinięty. Zamiast tego skup się na abstrahowaniu różnych składników operacji. Jeśli przerwiesz operację na części, zauważysz, że istnieją dwa komponenty symetryczne: obracanie listy w lewo i obracanie listy w prawo. Operacja, którą chcesz zdefiniować, iteruje prawą rotację określoną liczbę razy na niektórych listach. Sugeruje to, że pożądana operacja może być określona przez przy określona liczba iteracji z lewej albo lub odpowiedni obrót. Na przykład,

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 

Answer 4

Korzystanie cycle tutaj wydaje się dobre: ​​

shifts n xs = take (n+1) $ shifts' (cycle xs) 
    where 
    len = length xs 
    shifts' ys = take len ys:shifts' (drop (len-1) ys) 

Answer 5

Wydaje się, że wolą naprawić swój kod niż zacząć od nowa, tak rzućmy okiem na kodzie.Po pierwsze, głównym lista krojenia:

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

Teraz reverse (take i (reverse xs)) trwa i elementów z końca listy, ale odwrócić listę dwa razy, aby osiągnąć ten cel, a byłoby lepiej zrobić drop (length xs - i) xs. Podobnie można wdrożyć reverse (drop i (reverse xs))) jako take (length xs - i) xs. To daje nam

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

Teraz kod \i->[1..n]<=n nie ma sensu, ponieważ porównuje listę [1..n] z n, który nie może pracować. Myślę, że próbujesz utworzyć pętlę, w której i działa od 1 do n, co jest dobrym planem. Użyjmy wyrażeń listowych, aby uzyskać te chcieliśmy:

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

ale teraz mamy uruchomiony od 1 do długości listy, ale wyrzucać numery powyżej n, które byłyby lepiej napisany

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

To pozwala n być więcej niż length xs, ale nie widzę tu dużego problemu, możemy to sprawdzić na początku.

Wskazówka teraz, że mamy tylko używasz i w postaci (length xs - i) i naprawdę jesteśmy przeliczania length xs strasznie dużo więcej niż powinniśmy, więc zamiast pozwolić i bieg z 1 do n i używając length xs - i, Dlaczego po prostu nie mają j=length xs -i tak j biegnie od length xs do length xs - n:

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

który działa, ponieważ na przykład [6,5..1] == [6,5,4,3,2,1]

Byłoby neater zrobić

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

a może chcesz take więcej niż chcesz zrobić arytmetyki, więc możemy użyć:

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

która ma dodatkową zaletę cię powstrzymuje robisz zbyt wiele, zatrzymujesz się, gdy wrócisz na początek.

Chciałbym zmienić nazwę funkcji z generatingListforRightShifting do rotationsR, dając

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

Który daje rotationsR 6 [1..4] == [[1,2,3,4],[4,1,2,3],[3,4,1,2],[2,3,4,1],[1,2,3,4]].

Lewy obrót będzie wyglądać prościej:

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

---

dygresja: Nie mogłem się powstrzymać, przepraszam, i zacząłem ponownie.

ja nadal nie podoba wszystko, co spada i biorąc za każdym razem, wolałbym pop nieskończenie wiele kopii xs obok siebie (cycle xs) i podjąć nieskończenie wiele tails tego, siekanie je wszystkie odpowiednią długość, ale po prostu podaj pierwsze n:

obrótL 'n xs = niech l = długość xs w weź n. map (weź l). ogony. Cykl xs

Ponieważ oceny leniwe $, tylko skończoną ilość cycle xs kiedykolwiek zostanie obliczona ale ten może biec i biec: rotationsL' 10 [1..4] daje:

[[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]] 

Byłoby miło zrobić prawo w ten sposób również, ale nie działa, ponieważ musiałbym zacząć na końcu nieskończonej listy i wracać do pracy. Załóżmy, ponowne swój rewers, wziąć co trzeba, znowu odwrócić tricka, choć:

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

---

Undigression: Jeśli wolisz trzymać bliżej do oryginalnego kodu, można zrobić

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

Answer 6

znajdę lewy obrót jest bardzo prosta za pomocą splitAt:

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

> rotateLeft 2 "Hello World!" 
>>> "llo World!He"