## List Rotation

### March 27, 2020

[ I’ve been busy at work this week with virus stuff. I’m working at home, which is less productive than at the office. And we are making accommodations regarding the virus for our students, which requires a lot of urgent work. So, a quick little exercise today. ]

Given a length-n list like (a b c d e), the rotations of the list are the n lists (a b c d e), (b c d e a), (c d e a b), (d e a b c), and (e a b c d), in any order.

Your task is to write a program that takes a list and returns its rotations. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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