## 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