Permutation

The following spaghetti prints all permutations of a string ("abcd"). I wrote it as an example to show the benefit of structured programming in my class.

#include <iostream>
using namespace std;
int main()
{
        char c[] = "abcd\n";
        int size = sizeof(c) - 2;
        int n[size + 1];
        n[size] = 1;
        int idx = size;
        char t;
new_round:
        for (int i = 0; i < idx; i ++) n[i] = i + 1;
        cout << c;
start_shift:
        idx = 0;
        t = c[0];
shift_next:
        if (n[idx]) goto shift_done;
        idx ++;
        c[0] = c[idx];
        c[idx] = t;
        t = c[0];
        goto shift_next;
shift_done:
        n[idx] --;
        if (idx == size) return 0;
        if (n[idx] == 0) goto start_shift;
        goto new_round;
}

The structured version is as follows:

#include <iostream>
using namespace std;
int main()
{
        char c[] = "abcd\n";
        int size = sizeof(c) - 2;
        int n[size + 1];
        n[size] = 1;
        int idx = size;
        char t;
        do {
                if (n[idx]) {
                        for (int i = 0; i < idx; i ++) n[i] = i + 1;
                        cout << c;
                }
                idx = 0;
                t = c[0];
                while (n[idx] == 0) {
                        idx ++;
                        c[0] = c[idx];
                        c[idx] = t;
                        t = c[0];
                }
                n[idx] --;
        } while (idx < size);
        return 0;
}

The idea is to rotate a string by n times, where n is the length of the string. While, before each rotation, rotate the n-1 substring at the front n-1 times. And while, before each rotation, rotate the n-2 substring at the front n-2 times. And so on... We can see that this is more elegantly done recursively:

#include <iostream>
using namespace std;
char c[] = "abcd\n";
int size = sizeof(c) - 2;
void rotate(int l)
{
        char ch = c[l - 1];
        for (int i = l - 1; i; i --) c[i] = c[i - 1];
        c[0] = ch;
}
void perm(int l)
{
        if (l == 1) cout << c;
        else for (int i = 0; i < l; i ++) {
                perm(l - 1);
                rotate(l);
        }
}
int main()
{
        perm(size);
        return 0;
}

The above thinking counts on the string to have all distinct chars. When this isn't the case, a different approach is to consider the lexical order of the permutations. From a given permutation, we simply need to figure out the next in the lexical order until the order is "maximized". It turns out that this is in the C++ STL. My reimplementation is as follows:

#include <iostream>
using namespace std;
void swap(char & a, char & b)
{
        char c = a;
        a = b;
        b = c;
}
// increase the order of string
bool incr(char * str, size_t len)
{
        size_t i = 1;
        while (i < len && str[i - 1] >= str[i]) i ++;
        if (i == len) return false; // no kink
        // found a kink
        size_t j = i - 1;
        while (j > 0 && str[j - 1] < str[i]) j --; // size kink
        swap(str[i], str[j]); // shave kink
        // reverse rest
        for (i --, j = 0; j < i; i --, j ++) swap(str[i], str[j]);
        return true;
}
int main()
{
        char c[] = "aabbc\n";
        int size = sizeof(c) - 2;
        do cout << c; while (incr(c, size));
}