Skip to content

Instantly share code, notes, and snippets.

@ElementW
Created December 13, 2015 13:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ElementW/097989944093d825bdef to your computer and use it in GitHub Desktop.
Save ElementW/097989944093d825bdef to your computer and use it in GitHub Desktop.
Function to output all next permutations of a given string, part of my C exercices
void anagrammes(char *s) {
/* Pask' trouver des algorithmes écrits en français c'est inefficace,
* voici la traduction en C du pseudocode donné par
* https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order */
const int n = longueur(s);
puts(s);
while (1) {
int i, k = -1, l;
char c;
/* Find the largest index k such that a[k] < a[k + 1].
* If no such index exists, the permutation is the last permutation. */
for (i = n-2; i >= 0; --i) {
if (s[i] < s[i + 1]) {
k = i;
break;
}
}
if (k == -1) {
break;
}
/* Find the largest index l greater than k such that a[k] < a[l]. */
for (l = n-1; s[k] >= s[l] && l > k; --l);
/* Swap the value of a[k] with that of a[l]. */
c = s[k];
s[k] = s[l];
s[l] = c;
/* Reverse the sequence from a[k + 1] up to and including the final element a[n]. */
l = (n - (++k)) / 2;
for (i = n-1; k <= l; ++k, --i) {
c = s[k];
s[k] = s[i];
s[i] = c;
}
puts(s);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment