## List Rotation

### March 27, 2020

This is easy:

```(define (rots xs)
(define (rot1 xs)
(append (cdr xs) (list (car xs))))
(do ((n (length xs) (- n 1))
(zs (list xs) (cons (rot1 (car zs)) zs)))
((= n 1) zs)))```
```> (rots '(a b c d e))
((e a b c d)
(d e a b c)
(c d e a b)
(b c d e a)
(a b c d e))```

You can run the program at https://ideone.com/CLMGeG.

Pages: 1 2

### 13 Responses to “List Rotation”

1. chaw said

Here is a simple solution in standard R7RS Scheme and a couple of
helpers from SRFI 1. It uses a slightly different approach than the
one in the sample solution by @progammingpraxis (which doesn’t handle
the empty-list case).

``` (import (scheme base) (scheme write) (only (srfi 1) circular-list take)) (define (demo proc) (for-each (lambda (lst) (display lst) (newline) (display (list-rotations lst)) (newline) (newline)) '((a b c d e) () (a) (a a)))) (define (list-rotations lst) (let ((n (length lst))) (if (zero? n) '() (let loop ((clst (apply circular-list lst)) (nrots 0) (rots '())) (if (>= nrots n) rots (loop (cdr clst) (+ nrots 1) (cons (take clst n) rots))))))) (demo list-rotations) ```

Output:

``` (a b c d e) ((e a b c d) (d e a b c) (c d e a b) (b c d e a) (a b c d e)) () () (a) ((a)) (a a) ((a a) (a a)) ```

2. Steve said

Klong version

```
l::[:a :b :c :d :e]
[:a :b :c :d :e]
n::#l
5
l2::[];n{l2::l2,,n#x_(n*2)#l;x+1}:*0;l2
[[:a :b :c :d :e] [:b :c :d :e :a] [:c :d :e :a :b] [:d :e :a :b :c] [:e :a :b :c :d]]

```
3. Martin said

Here’s a very simple solution in Racket

```
(define (rotate-helper xs ys)
(cond
[(eq? (length ys) (length xs)) ys]
[else (rotate-helper xs (append ys (cons (append (list-tail xs (length ys)) (take xs (length ys))) '())))]))

(define (rotate xs)
(rotate-helper xs '()))

```
4. matthew said

Haskell one-liner, which handles infinite lists as well:

```Prelude Data.List Control.Monad> rotations = zipWith (++) <\$> tails <*> inits
[[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4]]
Prelude Data.List Control.Monad> take 5 (map (take 5) (rotations [1..]))
[[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7],[4,5,6,7,8],[5,6,7,8,9]]
```
5. Steve said

Klong, version 2

```
:"Found a rotate function"

l
[:a :b :c :d :e]
n::#l
5
:"Rotate list between n rows of (n+1) elements"
(n,(n+1)):^l
[[:a :b :c :d :e :a] [:b :c :d :e :a :b] [:c :d :e :a :b :c] [:d :e :a :b :c :d] [:e :a :b :c :d :e]]

:"Do that again but trim each row by the last element"
{n#x}'(n,(n+1)):^l
[[:a :b :c :d :e] [:b :c :d :e :a] [:c :d :e :a :b] [:d :e :a :b :c] [:e :a :b :c :d]]

```
6. Daniel said

Here’s a solution in Common Lisp, using the handling proposed by @matthew in an earlier problem to prevent duplicates.

(defun rotations (l)
(if (null l)
(list)
(let ((a (concatenate ‘list l l))
(n (length l)))
(labels ((rec (b)
(let ((c (subseq b 0 n)))
(if (equal c l)
(list)
(cons c (rec (cdr b)))))))
(cons (subseq a 0 n) (rec (cdr a)))))))

Example:

```CL-USER> (rotations '())
NIL
CL-USER> (rotations '(1 2 3))
((1 2 3) (2 3 1) (3 1 2))
CL-USER> (rotations '(1 1 1))
((1 1 1))
CL-USER> (rotations '(1 2 1 2))
((1 2 1 2) (2 1 2 1)
```
7. Daniel said

Here it is again, hopefully with the correct indentation.

```(defun rotations (l)
(if (null l)
(list)
(let ((a (concatenate 'list l l))
(n (length l)))
(labels ((rec (b)
(let ((c (subseq b 0 n)))
(if (equal c l)
(list)
(cons c (rec (cdr b)))))))
(cons (subseq a 0 n) (rec (cdr a)))))))
```
8. Daniel said

One last time, hopefully correct now. I used emacs—which I don’t use often—for its SLIME plugin. I didn’t realize I was using tabs as opposed to spaces.

```(defun rotations (l)
(if (null l)
(list)
(let ((a (concatenate 'list l l))
(n (length l)))
(labels ((rec (b)
(let ((c (subseq b 0 n)))
(if (equal c l)
(list)
(cons c (rec (cdr b)))))))
(cons (subseq a 0 n) (rec (cdr a)))))))
```
9. matthew said

@Daniel: if you don’t know already, “(setq-default indent-tabs-mode nil)” in your .emacs will sort that out (not tabs in existing files – “M-x untabify” will do that for the current buffer.

10. Richard A. O'Keefe said

Here it is in SML, using a ‘t vector instead of a ‘t list as input,
and a ‘t slice list instead of a ‘t list list as output.

fun rotations v =
let val n = Vector.length v
val s = Vector.concat([v, v])
in List.tabulate(n, fn offset => VectorSlice.slice(s, offset, SOME n))
end

The key point is that this takes O(n) time and space.
The same technique works in Common Lisp using displaced arrays.

11. Ashwin said

input = “abcd”

str1 = input
if len(input) > 1:
for i in range(len(input)):
str2 = str1[1:]+str1[0]
print(str2)
str1 = str2

12. Tim said

A Scheme solution that works by splitting the list into la and lb parts and iterating the breakpoint from left to right.

```(define (rotations l)
(let loop ((la '())
(lb l))
(if (null? lb)
'()
(cons (append lb la)
(loop (append la (list (car lb)))
(cdr lb))))))
```
13. David Oz said

Here is a solution in Python
n = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’]

def list_rotation(n):
for i in range(len(n)):
popped = n.pop(0)
n.append(popped)
print(n)

list_rotation(n)