String Rotations

February 28, 2020

A string like abc has three rotations: abc, bca, and cab.

Your task is to write a program that computes all the rotations of a string. 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

7 Responses to “String Rotations”

  1. matthew said

    The suggested solution doesn’t take into account a string that non-trivially rotates to itself.

    Here’s some Python that does the right thing. Note the ‘1’ offset for the find:

    >>> rotations = lambda s: [ss[i:i+len(s)] for ss in [s+s] for i in range(ss.find(s,1))]
    >>> rotations("a")
    ['a']
    >>> rotations("foobar")
    ['foobar', 'oobarf', 'obarfo', 'barfoo', 'arfoob', 'rfooba']
    >>> rotations("foofoo")
    ['foofoo', 'oofoof', 'ofoofo']
    
  2. chaw said

    Here is a simple solution using R7RS Scheme and a few well-known
    procedures from SRFI 1.

    (import (scheme base)
            (scheme write)
            (only (srfi 1)
                  iota circular-list take drop))
    
    (define (string-rotations str)
      (let ((n (string-length str))
            (clst (apply circular-list (string->list str))))
        (map (lambda (offset)
                (list->string (take (drop clst offset) n)))
             (iota n))))
    
    (write (string-rotations "abc"))
    (newline)
    (write (string-rotations "Hello, World!"))
    (newline)
    

    Output:

    ("abc" "bca" "cab")
    ("Hello, World!" "ello, World!H" "llo, World!He" "lo, World!Hel"
     "o, World!Hell" ", World!Hello" " World!Hello," "World!Hello, "
     "orld!Hello, W" "rld!Hello, Wo" "ld!Hello, Wor" "d!Hello, Worl"
     "!Hello, World")
    

  3. Pascal Bourguignon said
    ;; With this exercise we will demonstrate the use of Common Lisp displaced arrays.
    
    ;; Instead of creating a lot of strings, we will create displaced
    ;; arrays that will refer all to the same vector of character.
    
    ;; However, CL can displace an array only to a single array, so we
    ;; will have to create the storage string as the duplicated
    ;; concatenation of the original string.
    
    ;; This is therefore O(len) in storage instead of O(len²).
    
    (defun string-rotations (string)
      (let ((2strings (concatenate 'string string string)))
        (loop
          :with len := (length string)
          :for offset :below len
          :collect (make-array len :displaced-to 2strings :displaced-index-offset offset))))
    
    (string-rotations "abc")
    --> ("abc" "bca" "cab")
    
    ;; Note that mutating the storage will obviously appear to mutate the
    ;; strings that use the same storage, but since the characters are
    ;; duplicated, they're not all in all the rotations:
    
    (let ((rotations (string-rotations "Hello")))
      (print rotations)
      (setf (aref (first rotations) 3) #\X)
      (print rotations)
      (terpri))
    
    ("Hello" "elloH" "lloHe" "loHel" "oHell") 
    ("HelXo" "elXoH" "lXoHe" "XoHel" "oHell") 
    --> nil
    
    
  4. Daniel said

    Here’s a solution in C, using the handling proposed by @matthew to prevent duplicates.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(int argc, char* argv[]) {
      if (argc != 2) return EXIT_FAILURE;
      int n = strlen(argv[1]);
      if (n == 0) return EXIT_SUCCESS;
      char* s = malloc(n * 2);  // no null termination
      memcpy(s, argv[1], n);
      memcpy(s + n, argv[1], n);
      char* end = strnstr(s + 1, argv[1], n * 2 - 1);
      for (int i = 0; s + i < end; ++i) {
        printf("%.*s\n", n, s + i);
      }
      free(s);
      return EXIT_SUCCESS;
    }
    

    Example:

    $ ./a.out aaaa
    aaaa
    
    $ ./a.out praxis
    praxis
    raxisp
    axispr
    xispra
    isprax
    spraxi
    
    $ ./a.out foofoo
    foofoo
    oofoof
    ofoofo
    
  5. Steve said
    
    Klong
    
            s::"abc"
    "abc"
            n::#s
    3
            s::((2*n)-1):^s
    "abcab"
            n#0_s
    "abc"
            n#1_s
    "bca"
            n#2_s
    "cab"
            {[n s];s::x;n::#s;s::((2*n)-1):^s;{n#x_s}'!n}'["Praxis" "abc" "Hello World!"]
    [["Praxis" "raxisP" "axisPr" "xisPra" "isPrax" "sPraxi"] ["abc" "bca" "cab"] ["Hello World!" "ello World!H" "llo World!He" "lo World!Hel" "o World!Hell" " World!Hello" "World!Hello " "orld!Hello W" "rld!Hello Wo" "ld!Hello Wor" "d!Hello Worl" "!Hello World"]]
    
    
  6. Globules said

    Here’s a Haskell version (that allows duplicates).

    import Control.Arrow ((&&&))
    import Data.List (inits, tails)
    
    rots :: [a] -> [[a]]
    rots = init . uncurry (zipWith (++)) . (tails &&& inits)
    
    main :: IO ()
    main = mapM_ (print . rots) ["", "a", "ab", "abc"]
    
    $ ./rots
    []
    ["a"]
    ["ab","ba"]
    ["abc","bca","cab"]
    
  7. Sam Claflin said

    Python Solutio

    def rotate_string(string):
        for i in range(0, len(string)):
            if i == 0:
                print(string)
            else:
                string = string[-1] + string[:len(string) - 1]
                print(string)
    
    
    rotate_string("hello, this program rotates strings")
    

    OUTPUT –>

    hello, this program rotates strings
    shello, this program rotates string
    gshello, this program rotates strin
    ngshello, this program rotates stri
    ingshello, this program rotates str
    ringshello, this program rotates st
    tringshello, this program rotates s
    stringshello, this program rotates
    stringshello, this program rotates
    s stringshello, this program rotate
    es stringshello, this program rotat
    tes stringshello, this program rota
    ates stringshello, this program rot
    tates stringshello, this program ro
    otates stringshello, this program r
    rotates stringshello, this program
    rotates stringshello, this program
    m rotates stringshello, this progra
    am rotates stringshello, this progr
    ram rotates stringshello, this prog
    gram rotates stringshello, this pro
    ogram rotates stringshello, this pr
    rogram rotates stringshello, this p
    program rotates stringshello, this
    program rotates stringshello, this
    s program rotates stringshello, thi
    is program rotates stringshello, th
    his program rotates stringshello, t
    this program rotates stringshello,
    this program rotates stringshello,
    , this program rotates stringshello
    o, this program rotates stringshell
    lo, this program rotates stringshel
    llo, this program rotates stringshe
    ello, this program rotates stringsh

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: