8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Oops, I just found that there is a phrase to describe the result I want: lexicographically larger permutation..., hope this help your understanding... \$\endgroup\$ – Niing Mar 10 '18 at 4:25
  • \$\begingroup\$ And the function printPermutation will print the range $$[k, m]$$, not $$[k, m)$$, sorry if this make you confused... \$\endgroup\$ – Niing Mar 10 '18 at 4:29
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – Eric Lippert Mar 10 '18 at 16:27
  • \$\begingroup\$ @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... \$\endgroup\$ – Niing Mar 11 '18 at 3:21
13
\$\begingroup\$

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).
\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.