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

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)