A beautiful and easy way of permutation with recursion

Question

I want to share a better version of permutation with you.

Yesterday, when I was reading Horowitz's Fundamentals of Data Structures In C++, and I noticed that the result of the code, at page 32, in the book is not what I want.

For example, if I have an array of {'a', 'b', 'c'}, then the result it provides is:

abc
acb
bac
bca
cba
cab

Notice that the last two cases don't fit what I want: when 'c' is fixed, all the other letters at its right should start from a, with relative order, \$a \lt b \lt c \lt \ldots \lt z\$, so the result should be:

...
cab
cba

Here is my code, which corrects the order with two modified swaps:

#include <iostream>
using namespace std;

void printPermutation(char *a, const int k, const int m);
void swap2(char *a, const int l, const int r);
void swap3(char *a, const int l, const int r);

int main() {
    char str[] = {'a', 'b', 'c', 'd', 'e'};
    printPermutation(&str[0], 0, sizeof(str)-1);
    return 0;
}

void printPermutation(char *a, const int k, const int m) {
    if (k == m) {
        for (int i = 0; i <= m; i++) {
            cout << a[i];
        }
        cout << endl;
    }
    else {
        for (int i = k; i <= m; i++) {
            // the code in the book just use swap, but I change them.
            swap2(a, k, i); // here
            printPermutation(a, k+1, m);
            swap3(a, k, i); // and here
        }
    }
}

// swap2 will move the element at index r to l,
// by continuously swap with element at its left
void swap2(char *a, const int l, const int r) {
    for (int i = r; l < i; i--) {
        swap(a[i], a[i-1]);
    }
}

// The same concept with swap2, but from left to right
void swap3(char *a, const int l, const int r) {
    for (int i = l; i < r; i++) {
        swap(a[i], a[i+1]);
    }
}

How can I further simplify the code?

I like the idea that the author used recursion to make things beautifully simple. But to achieve the result I want as described above, I have to add two additional, a little bit similar, functions.

Answer 1

The simpler code would look something like this:

#include <string>
#include <algorithm>
#include <iostream>

int main() {
    std::string s = "abcde";

    while (std::next_permutation(s.begin(), s.end()))
        std::cout << s << "\n";
}

If you wanted to do something on the same general order as a Python generator, you'd use C++'s new coroutine support. What's currently included is (by intent) very low-level, so you need a fair amount of infrastructure on top of it before it's easy to write a Python-like generator.

To keep from getting buried in details you probably don't care a lot about (right now) I'll use Kenny Kerr's Generator class (the first 173 lines, transplanted into a header). Using it, we get something like this:

#include "generator.hpp"
#include <iostream>
#include <string>
#include <algorithm>

template <class T>
generator<T> perm(T initial) {
    while (std::next_permutation(initial.begin(), initial.end()))
        co_yield initial;
}

int main() { 
    using namespace std::literals;
    for (auto const &i : perm("abcde"s))
        std::cout << i << "\n";
}

As to your code, a few points jump out:

1. Don't use std::endl. It flushes the stream, which you almost never want. Just use '\n'. On the rare occasion that you do want to flush the stream, use std::flush.
2. The C library reserves most names that start with str, so it's probably better to avoid using that as a name.
3. using namespace std; is widely considered a problem except under a small number of rather unusual circumstances.
4. If you really want to do this (more) on your own, you might want to take a look at std::rotate, which can replace both your swap2 and swap3. std::rotate will also typically be more efficient than your implementation.
5. swap2 and swap3 strike me as poor names. At first glance, it seems like rotate_left and rotate_right would probably be better names (but also see above).

Answer 2

I find permutations both fun and fascinating, so this is pretty cool.

I was going to say most of what @Jerry Coffin said, so rather than repeat all that, I'll just point out a few things:

• Your str variable in main() looks a lot like a typical NUL-terminated C string, but isn't. It's even named str furthering the confusion. If a future developer were to call, say, strlen() on it, it would likely crash. I'd rename it.
• Your variable names are cryptic. What are k and m in printPermutation()? They're indexes into a (also a terrible name) for where to start and end the permutation. I suggest renaming them something like startIndex and endIndex.
• Likewise with l and r in swap2() and swap3().
• As pointed out, swap2() and swap3() actually rotate rather than swap. Regardless of that, the names imply that they're doing something with 2 and 3 parameters, but they aren't. You should avoid just adding a number to an existing similar function to get a new name. This is an antipattern that persists in programming.

One way you could make this more useful is to make a templated function for permutations so that they work on containers of any type. (I guess that's what std::permutation() does - but it's always fun to learn on your own!)