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.
Programming Praxis 
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:
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]]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 '()))Haskell one-liner, which handles infinite lists as well:
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]]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.
(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)))))))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)))))))@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.
(define (rotations l) (let loop ((la '()) (lb l)) (if (null? lb) '() (cons (append lb la) (loop (append la (list (car lb))) (cdr lb))))))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)