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.

Pages: 1 2

13 Responses to “List Rotation”

  1. chaw said

    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:

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

  2. Steve said

    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]]
    
    
  3. Martin said

    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 '()))
    
    
  4. matthew said

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

    Prelude Data.List Control.Monad> rotations = zipWith (++) <$> tails <*> inits
    Prelude Data.List Control.Monad> rotations [1..4]
    [[1,2,3,4],[2,3,4,1],[3,4,1,2],[4,1,2,3],[1,2,3,4]]
    Prelude Data.List Control.Monad> take 5 (map (take 5) (rotations [1..]))
    [[1,2,3,4,5],[2,3,4,5,6],[3,4,5,6,7],[4,5,6,7,8],[5,6,7,8,9]]
    
  5. Steve said

    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]]
    
    
  6. Daniel said

    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:

    CL-USER> (rotations '())
    NIL
    CL-USER> (rotations '(1 2 3))
    ((1 2 3) (2 3 1) (3 1 2))
    CL-USER> (rotations '(1 1 1))
    ((1 1 1))
    CL-USER> (rotations '(1 2 1 2))
    ((1 2 1 2) (2 1 2 1)
    
  7. Daniel said

    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)))))))
    
  8. Daniel said

    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)))))))
    
  9. matthew said

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

  10. Richard A. O'Keefe said

    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.

  11. Ashwin said

    input = “abcd”

    str1 = input
    if len(input) > 1:
    for i in range(len(input)):
    str2 = str1[1:]+str1[0]
    print(str2)
    str1 = str2

  12. Tim said

    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))))))
    
  13. David Oz said

    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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: