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