-
Follow
Following
Already have a WordPress.com account? Log in now.
A collection of etudes, updated weekly, for the education and enjoyment of the savvy programmer
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
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