String Rotations
February 28, 2020
The heart of our program is a function that generates all the rotations of a list; it first doubles the list, then takes successive cdrs of the doubled list:
(define (rots xs)
(let ((len (length xs)))
(do ((xxs (append xs xs) (cdr xxs))
(rots (list) (cons (take len xxs) rots))
(n len (- n 1))) ((zero? n) rots))))
Given that, it is easy to find the rotations of a string:
(define (string-rotations str) (map list->string (rots (string->list str))))
Here is an example:
> (string-rotations "Praxis")
("sPraxi" "isPrax" "xisPra" "axisPr" "raxisP" "Praxis")
You can run the program at https://ideone.com/WD67A9.
Programming Praxis 
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']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");; 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") --> nilHere’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:
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"]]Here’s a Haskell version (that allows duplicates).
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