home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1947 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  2.6 KB
  1. From: mday@iconsys.uucp (Matt Day)
  2. Newsgroups: alt.sources
  3. Subject: Permutation generator
  4. Message-ID: <1990Oct12.172633.8855@iconsys.uucp>
  5. Date: 12 Oct 90 17:26:33 GMT
  6.  
  7. I've seen requests for a permutation generator several times in other groups,
  8. so I thought I'd post my algorithm and see what everybody thinks.  Before I
  9. wrote this version, I came up with a couple of algorithms that needed to
  10. allocate a whole bunch of memory for an array, or needed to recurse a zillion
  11. times.  This algorithm doesn't need to do either, therefore it's quite fast
  12. and efficient.  I had a lot of fun working on this program, and I'd be happy
  13. to discuss different methods that others may have.  I haven't included a
  14. Makefile or anything, since such a simple program, so just save this article
  15. off, delete my ramblings, and compile away (it should compile on about any
  16. system).  Please bum my code and send patches, optimize, optimize!  Enjoy!
  17.  
  18. By the way, I have a version written in perfect ANSI C, if anyone cares..
  19. ---------------------------- Begin permute.c --------------------------------
  20. /*
  21.  * permute - Generates all permutations of a given string.
  22.  * Matthew T. Day (mday@iconsys.icon.com), 9/27/90.
  23.  */
  24.  
  25. #include <stdio.h>
  26.  
  27. int len;
  28. char tmp;
  29.  
  30. /* Simple macro for swapping two variables. */
  31. #define swap(a, b) tmp = (a), (a) = (b), (b) = tmp
  32.  
  33. /*
  34.  * The permutation generator.  This routine immediately recurses, passing
  35.  * itself a copy of the string and its level of recursion, until it has
  36.  * recursed to a depth equal to the length of the string.  At that point it
  37.  * loops, printing the string and shifting to the left the character located
  38.  * in the array offset by the recursion level.  When the character being
  39.  * shifted reaches the beginning of the string, it drops back to the
  40.  * previous level of recursion.
  41.  */
  42. void permute(string, index)
  43. register char *string;
  44. register int index;
  45. {
  46.     register int level = index, printing = !string[index + 1];
  47.     register char *copy;
  48.  
  49.     if (!(copy = (char *) malloc(len * sizeof(char) + 1))) {
  50.         (void) fputs("Error: Out of memory.", stderr);
  51.         exit(1);
  52.     }
  53.  
  54.     (void) strcpy(copy, string);
  55.  
  56.     do {
  57.         if (printing) (void) puts(copy);
  58.         else permute(copy, level + 1);
  59.         if (index) swap(copy[index], copy[index - 1]);
  60.     } while (index--);
  61. }
  62.  
  63. void main(argc, argv)
  64. int argc;
  65. char **argv;
  66. {
  67.     if (argc != 2) {
  68.         (void) fputs("Usage: permute string\n", stderr);
  69.         exit(1);
  70.     }
  71.  
  72.     len = strlen(argv[1]);
  73.     permute(argv[1], 0);
  74.  
  75.     exit(0);
  76. }
  77. ------------------------------- End permute.c --------------------------------
  78. -- 
  79. - Matthew T. Day, Sanyo/Icon, mday@iconsys.icon.com || uunet!iconsys!mday
  80.