All rotations of a string with ranges – #thatsarotate

Posted: July 14, 2021 in Competitive Programming, Programming Recipes
Tags: , , , ,

A common programming puzzle consists in printing all rotations of a string. For example, all rotations of abc are:

abc
bca
cab

Intuitively, every rotation is a substring of the original string concatenated with itself (last character excluded):

abc + ab 
= abcab
  abc
   bca
    cab

Another example:

input: abcdefgh

abcdefghabcdefg
abcdefgh
 bcdefgha
  cdefghab
   defghabc
    efghabcd
     fghabcde
      ghabcdef
       habcdefg

Indeed, the number of rotations is equal to the length of the string.

The pattern above could be mimicked with ranges quite easily.

We first create a temporary string as the concatenation of the original string with itself excluding the last character:

std::string input = "abcd";
const auto len = size(input);
auto tmp = input + input.substr(0, len - 1); // abcdabc

And then we print all the sliding windows of dimension len.

That’s a views::sliding!

std::string input = "abcd";
const auto len = size(input);
auto tmp = input + input.substr(0, len - 1);
std::cout << (tmp | views::sliding(len));

An alternative solution to avoid the temporary string consists in generating every rotation lazily.

Thinking range-fully, the string concatenated with itself can be seen as an application of views::cycle. We can still use views::sliding but we must take only len windows.

Let me drive you towards the solution.

First of all, we create the “infinite” string:

std::string input = "abcd";
const auto len = size(input);
input | views::cycle; // ['a', 'b', 'c', 'd', 'a', 'b', 'c', ... 

As before, now we apply sliding:

std::string input = "abcd";
const auto len = size(input);
input | views::cycle // ['a', 'b', 'c', 'd', 'a', 'b', 'c', ... ]
      | views::sliding(len); // [ ['a', 'b', 'c', 'd'], ['b', 'c', 'd', 'a'], ['c', 'd', 'a', 'b'] ... 

Finally, we take only (the first) len windows:

std::string input = "abcd";
const auto len = size(input);
auto rotations= 
  input | views::cycle // ['a', 'b', 'c', 'd', 'a', 'b', 'c', ... ]
        | views::sliding(len) // [ ['a', 'b', 'c', 'd'], ['b', 'c', 'd', 'a'], ['c', 'd', 'a', 'b'] ... 
        | views::take(len); // [ ['a', 'b', 'c', 'd'], ['b', 'c', 'd', 'a'], ['c', 'd', 'a', 'b'] , ['d', 'a', 'b', 'c'] ]

std::cout << rotations;

To conclude, let me make a quick digression on views::cycle.

views::cycle repeats the elements of a range cyclically:

views::cycle(views::single(1)); // [1, 1, 1, ... 

std::vector v = {1,2,3,4};
views::cycle(c); // [1, 2, 3, 4, 1, 2, 3, 4, 1, ... 

views::cycle makes an endless range from an input range, but it doesn’t change its cardinality.

A common question is how to repeat the entire range as-is, not the content. For example:

std::vector v = {1,2,3,4};
views::cycle( ??? ); // [ [1,2,3,4], [1,2,3,4], [1,2,3,4], ... 

Think about it for a moment.

To solve the puzzle, just remember that cycle repeats the elements of the input range. The trick now is to create a range containing the vector as the only element.

That’s a views::single!

std::vector v = {1,2,3,4};
views::cycle( views::single(v) );

However, this might be “inconvenient” because cycle repeats the std::vector as-is but sometimes we want the content of the vector instead:

std::vector v = {1,2,3,4};
std::cout << views::cycle( views::single(v) ); // no way

Here is a visualization of cycle:

views::cycle(views::single(1)); // [1, 1, 1, ... 

std::vector v = {1,2,3,4};
views::cycle(c); // [1, 2, 3, 4, 1, 2, 3, 4, 1, ... 

views::cycle(views::single(v)); // [v, v, v, v, ... 

However, we might want to generate the following, instead:

std::vector v = {1,2,3,4};
views::cycle( views::single( ??? ) ); // [ [1,2,3,4], [1,2,3,4], [1,2,3,4] ... 

Now the question is: how to turn such a vector into the range of its elements?!

That’s a views::all!

std::vector v = {1,2,3,4};
std::cout << views::all(v); // [1, 2, 3, 4]

views::all simply turns every range into the range of its elements. Basically, applying all to a container “erases” the type of the container. So, the answer to the puzzle is:

std::vector v = {1,2,3,4};
views::cycle( views::single( views::all(v) ) ); // [ [1,2,3,4], [1,2,3,4], [1,2,3,4] ... 

Indeed, views::all is often used for converting containers to ranges.

Edit: in a private conversation, Ruzena Gurkaynak sent an alternative (and more concise) way for getting the same result as above:

std::vector v = {1,2,3,4};
views::repeat(views::all(v)); // [ [1,2,3,4], [1,2,3,4], [1,2,3,4] ... 

Just a closing anecdote: when I started writing this blog post, my solution to the problem discussed was a bit different and more convoluted. While putting the idea into writing, I realized the puzzle could be solved more easily. If you are interested, here was my initial thought:

std::string input = "abcd";
const auto len = size(input);
auto cycled  = input | views::cycle;
auto rotations = views::iota(0u, len) | views::transform([=](auto i) {
   return cycled | views::drop(i) | views::take(len);
});

That’s all folks!

I hope you have enjoyed the article and please let me know your thoughts in the comments section below.

Comments
  1. Bartłomiej Filipek says:

    thanks for the examples! Do you have some github links? or maybe to compiler explorer? can this be emulated with C++20 Ranges? or only Ranges v3?

  2. kobica says:

    beautiful 🙂

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