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)