# A beautiful and easy way of permutation with recursion

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.

• Oops, I just found that there is a phrase to describe the result I want: lexicographically larger permutation..., hope this help your understanding... – Niing Mar 10 '18 at 4:25
• And the function printPermutation will print the range $$[k, m]$$, not $$[k, m)$$, sorry if this make you confused... – Niing Mar 10 '18 at 4:29
• I wrote a series of articles on elegant ways to produce permutations in C#; you might find it interesting. It starts here: ericlippert.com/2013/04/15/producing-permutations-part-one – Eric Lippert Mar 10 '18 at 16:27
• @EricLippert: I was stuck at part4, last line of second snippet, about why the item inserted is n-1 not n, and finally realize that your permutation start from 0... Now I can moving forward... – Niing Mar 11 '18 at 3:21

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).

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!)