Find all cyclic permutations of a string in O(n)

Question

Given the problem: Find all cyclic permutations of a string

For example: given a string: "abcd"

All the cyclic permutations of a string would be: "abcd", "dabc", "cdab", "bcda"

Here's what I have tried out:

for(int i = 0; i < str.size(); i++){
    permu.push_back(str);
    str.insert(0, 1, str[str.size()-1]);
    str.erase(str.end()-1);
}

I got Time-limit-exceeded since the insert and erase function takes O(n) making the overall solution O(n^2)

Is there anyway to solve this in O(n) or less?

If you write a vector of strings, the size of the output is n², there is no way to write n² characters in time O(n)... — Marc Glisse, Aug 09 '21 at 11:06
the size of output should be n strings, since it's a cyclic permutation — UTL, Aug 09 '21 at 11:08
sorry for the misunderstood, it's just 1 string with n characters — UTL, Aug 09 '21 at 11:09
Do you have to store them? is it the final output? or is it a intermediate result you use? — Jarod42, Aug 09 '21 at 11:10
So you probably have to find way without that. With `"abcdabc"`, you can have views of all the cyclic permutation. — Jarod42, Aug 09 '21 at 11:17
*"sorry for the misunderstood, it's just 1 string with n characters"*: Marc Glisse talked about **output**, not input. indeed, input is one string of `n` charecters, but **output** is `n` strings of `n` characters, so a total of `n²` characters. — Jarod42, Aug 09 '21 at 11:20
I once answered a question reagrding "Cyclic Permutation" https://stackoverflow.com/questions/61413541/using-sort-function-to-sort-vector-of-tuples-in-a-chained-manner/61414539#61414539 I am wondering, what this question has to do with "Cyclic Permutations"? It is just rotation. But maybe, I am wrong . . . — A M, Aug 09 '21 at 13:10

Botje · Answer 1 · 2021-08-09T12:18:59.630

4

You can use string_view to do it in O(n):

std::vector<std::string_view> get_perms(std::string& str) {
    auto orig_length = str.length();
    str += str;
    std::vector<std::string_view> ret;

    std::string_view sv{str};
    for (int i = 0; i < orig_length; i++) {
        auto sv2 = sv.substr(i, orig_length);
        ret.push_back(sv2);
    }
    return ret;
}

Taking a substring of a string_view is constant time, but you need to ensure the original string stays alive. This is why the function takes str as a non-const reference.

edited Aug 09 '21 at 12:18

answered Aug 09 '21 at 11:20

Botje

26,269
3
31
41

Notice that you iterate over permutations and no longer return them. I think OP split naively the big problem, resulting in bad algorithm. I'm not even sure we need the iteration for the actual problem. – Jarod42 Aug 09 '21 at 11:30
Updated to keep a vector of views. I was not sure of an elegant approach of keeping the string together with the permutations so I did not go that far. – Botje Aug 09 '21 at 11:48
Recommend not taking `str` as ref, but as value. That way you have the option to move something in, but also you have the option to retain the original string. – bitmask Aug 09 '21 at 12:59
@bitmask I would happily accept an edit that does so in an ergonomic fashion. The closest I got was returning a `tuple>`, but you then have to rely on the behavior of the string move constructor AND you're stuck with a variable you have no use for. – Botje Aug 09 '21 at 13:16
@Botje I see your point. Didn't really consider the most ergonomic way to get the string into the tuple. I suppose you could move the original argument into the tuple when constructing it (RAII), then only use the tuple's `0` member instead of `str`. – bitmask Aug 09 '21 at 13:20

score 0 · Accepted Answer · answered Aug 09 '21 at 11:56

0

Here's another approach if you don't want to create another string:

for(int i = 0; i < str.size(); i++)
    permu.push_back(str.substr(i) + str.substr(0, i));

answered Aug 09 '21 at 11:56

unglinh279

675
4
24

2

Definitely the most compact answer, but also O(n^2) since `substr` is linear in the count of characters... – Botje Aug 09 '21 at 12:00
And does extra allocations. – Jarod42 Aug 09 '21 at 12:05
1

@Botje i don't know much about "subtr" but it's the most compact and somehow works for me, I didn't get time_limit_exceeded using this. – UTL Aug 10 '21 at 12:18

Find all cyclic permutations of a string in O(n)

2 Answers2