lexicographic Permutations Algorithm
The survey of permutations of finite sets is an important subject in the fields of combinatorics and group theory. In elementary combinatorics, the K-permutations, or partial permutations, are the ordered agreements of K distinct components choose from a set. Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.
A first case in which apparently unrelated mathematical questions were study with the help of permutations happened around 1770, when Joseph Louis Lagrange, in the survey of polynomial equations, detected that property of the permutations of the beginnings of an equation are associated to the possibility to solve it. Fabian Stedman in 1677 described factorials when explaining the number of permutations of Bell in change ringing. The rule to determine the number of permutations of n objects was known in Indian culture around 1150.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void swap(char* left, char* right){
char temp = *left;
*left = *right;
*right = temp;
}
int compare (const void * a, const void * b){
return ( *(char*)a - *(char*)b );
}
void PrintSortedPermutations(char str[])
{
int strSize = strlen(str);
qsort(str, strSize, sizeof(char), compare);
int largerPermFound = 1;
do{
// 1. Print permutation
printf("%s\n", str);
// 2. Find rightmost char that is smaller than char to its right
int i;
for (i = strSize - 2; i >= 0 && str[i] >= str[i+1]; --i){}
// if we couldn't find one, we're finished, else we can swap
if (i >= 0){
// 3. find character at index j such that str[j] = min(str[k]) && str[k] > str[i] for all k > i
int j = i+1, k;
for(k=j; k<strSize && str[k]; k++){
if (str[k] > str[i] && str[k] < str[j])
j = k;
}
// 3. Swap chars at i and j
swap(&str[i], &str[j]);
// 4. Sort string to the right of i
qsort(str+i+1, strSize-i-1, sizeof(char), compare);
}
else largerPermFound = 0;
}
while(largerPermFound);
}
int main() {
int n; //size of string
scanf("%d\n",&n);
char str[n];
scanf("%s",str);
PrintSortedPermutations(str);
return 0;
}
