Skip to content

Instantly share code, notes, and snippets.

@ashelly
Created February 1, 2019 04:59
Show Gist options
  • Save ashelly/fcb59a063f9c8a940fdbb50a7102c84c to your computer and use it in GitHub Desktop.
Save ashelly/fcb59a063f9c8a940fdbb50a7102c84c to your computer and use it in GitHub Desktop.
Knuth 7.2.1.2: Algorithm L (Lexicographic Permutation Generation) in C.
static inline void Exchange(int* data, int a, int b) {
int temp = data[a];
data[a]=data[b];
data[b]=temp;
}
//generates all permutations of initially sorted array `a` with `n` elements
//returns 0 when no more permutations exist
int genPermutation(int a[], int n)
{
int l,j;
for (j = --n; j > 0 && a[j-1] >= a[j]; --j) { ; }
if (j == 0) return 0;
for (l = n; a[j-1] >= a[l]; --l) { ; }
Exchange(a, j-1, l);
while (j < n) { Exchange(a, j++ ,n--); }
return 1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment