home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / PERMUTE2.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  2KB  |  82 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. /*
  4. **  PERMUTE.C - prints all permutations of an input string
  5. **
  6. **  public domain demo by Jon Guthrie
  7. */
  8.  
  9. #include    <string.h>
  10. #include    <stdlib.h>
  11. #include    <stdio.h>
  12.  
  13. int     charcmp(char *, char *);
  14.  
  15. void    permute(char *, int, int);
  16.  
  17. int     main(int argc, char *argv[])
  18. {
  19.       int length;
  20.  
  21.       if (2 > argc)
  22.       {
  23.             puts("Usage: PERMUTE string");
  24.             abort();
  25.       }
  26.       
  27.       length = strlen(argv[1]);
  28.  
  29.       /* It only works if they're printed in order */
  30.  
  31.       qsort(argv[1], length, 1, (int(*)(const void *, const void *))charcmp);
  32.  
  33.       permute(argv[1], 0, length);
  34.       return 0;
  35. }
  36.  
  37.  
  38. /*
  39. **  This function prints all of the permutations of string "array"
  40. **  (which has length "len") starting at "start."
  41. */
  42.  
  43. void    permute(char *array, int start, int len)
  44. {
  45.       int j;
  46.       char    *s;
  47.  
  48.       if(start < len)
  49.       {
  50.             if(NULL == (s = malloc(len)))
  51.             {
  52.                   printf("\n\nMemory error!!!\a\a\n");
  53.                   abort();
  54.             }
  55.  
  56.             strcpy(s, array);
  57.             for(j=start ; j<len ; ++j)
  58.             {
  59.                   int     temp;
  60.  
  61.                   if((j == start) || (s[j] != s[start]))
  62.                   {     /* For each character that's different    */
  63.                         /* Swap the next first character with...  */
  64.                         /* the current first                      */
  65.                         temp = s[j];
  66.                         s[j] = s[start];
  67.                         s[start] = temp;
  68.                         permute(s, start+1, len);
  69.                   }
  70.             }
  71.             free(s);
  72.       }
  73.       else  puts(array);
  74. }
  75.  
  76.  
  77.  
  78. int charcmp(char *a, char *b)
  79. {
  80.       return(*a - *b);
  81. }
  82.