Wednesday, April 27, 2005

Permutation code on popular demand

I have been asked by several people individually to make the permutation code available on the blog. Well here goes (The code is in Java and contains the iterative and the recursive version)



/*
* Don Knuth's Permutation Algorithm
*/

public class permu {
int[] a;
int j, k, l, n;

permu(int n) {
a = new int[n+1];
this.n = n;

for (int i = 0; i <= n; i++)
a[i] = i;

}

void visit() {
for (int i = 1; i <= n; i++)
System.out.print(a[i] + " ");
System.out.println();
}

void swap(int j, int k) {
if (j == k) return;
int tmp = a[j];
a[j] = a[k];
a[k] = tmp;
}

//
// print all permutations of the numbers 1 to n
//
void permute() {

do {
visit();
j = n - 1;
while (j != 0 && a[j] >= a[j+1]) {
j--;
}
if (j == 0) break;

l = n;
while (a[j] >= a[l]) {
l--;
}

swap(j, l);
k = j+1;
l = n;
while (k < l) {
swap(k, l);
k++;
l--;
}
} while (j >= 0);
}

void rpermute(int k, int m) {

int i;

if (m == k) {
visit();
return;
}

for (i = k; i <= m; i++) {
swap(i, k);
rpermute(k+1, m);
swap(i, k);
}
}



public static void main(String [] args) {
int n;
if (args.length != 1) {
System.out.println("usage is permu ");
return;
} else {
n = Integer.parseInt(args[0]);
}

permu p = new permu(n);
p.permute();
permu p2 = new permu(n);
p2.rpermute(1, n);

}
}



Do you see the similarity with quicksort? For a good explanation of the algorithm see Don Knuth's Fascicle 4.

No comments:

Ranking and Unranking permutations

I've been a big fan of Skiena's Algorithm Design Manual , I recently found my first edition of the book (although I own the third ed...