## 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.

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

Output:

Klong version

Here’s a very simple solution in Racket

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

Klong, version 2

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:

Here it is again, hopefully with the correct indentation.

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.

@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.

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.

input = “abcd”

str1 = input

if len(input) > 1:

for i in range(len(input)):

str2 = str1[1:]+str1[0]

print(str2)

str1 = str2

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

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)