fork(30) download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. void swap(char* left, char* right)
  6. {
  7. 	char temp = *left;
  8. 	*left = *right;
  9. 	*right = temp;
  10. }
  11. int compare (const void * a, const void * b)
  12. {
  13.   return ( *(char*)a - *(char*)b );
  14. }
  15. void PrintSortedPermutations(char* inStr)
  16. {
  17. 	// Re-implementation of algorithm described here:
  18. 	// http://w...content-available-to-author-only...s.org/lexicographic-permutations-of-string/
  19. 	int strSize = strlen(inStr);
  20. 	// 0. Ensure input container is sorted
  21. 	qsort(inStr, strSize, sizeof(char), compare);
  22.  
  23.  
  24. 	int largerPermFound = 1;
  25. 	do{
  26. 		// 1. Print next permutation
  27. 		printf("%s\n", inStr);
  28. 		// 2. Find rightmost char that is smaller than char to its right
  29. 		int i;
  30.         for (i = strSize - 2; i >= 0 && inStr[i] >= inStr[i+1]; --i){}
  31.  
  32.         // if we couldn't find one, we're finished, else we can swap somewhere
  33.         if (i > -1)
  34.         {
  35.         	// 3 find character at index j such that 
  36.         	// inStr[j] = min(inStr[k]) && inStr[k] > inStr[i] for all k > i
  37.         	int j = i+1;
  38.         	int k;
  39.         	for(k=j;k<strSize && inStr[k];++k)
  40.         	{
  41.         		if (inStr[k] > inStr[i] && inStr[k] < inStr[j])
  42.     				j = k;
  43.         	}
  44.  
  45.         	// 3. Swap chars at i and j
  46.         	swap(&inStr[i], &inStr[j]);
  47.  
  48.         	// 4. Sort string to the right of i
  49.         	qsort(inStr+i+1, strSize-i-1, sizeof(char), compare);
  50.         }
  51.         else
  52.         {
  53.         	largerPermFound = 0;
  54.         }
  55. 	}while(largerPermFound);
  56. }
  57.  
  58. int main(void) {
  59. 	char str[] = "abc";
  60.  
  61. 	PrintSortedPermutations(str);
  62. 	return 0;
  63. }
  64.  
Success #stdin #stdout 0s 2052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
abc
acb
bac
bca
cab
cba
https://ideone.com/3WHHtG
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!