Created
December 13, 2015 13:42
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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