Tuesday, April 26, 2011

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));
}
```