home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / PERMUTE1.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  4KB  |  119 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<string.h>
  6.  
  7. /*  chouse_n ( char *strng, int length) returns a pointer to a string of   */
  8. /*  length characters chosen from "strng" , duplicate chars in "strng" are */
  9. /*  significant.  Strings are generated in lexical order.                  */
  10. /*  First call, call with *strng. each subsequent call, call with NULL,    */
  11. /*  returns one combination. Calls after all combinations have been        */
  12. /*  returned return NULL.  Will return NULL for errors.                    */
  13. /*  not very defensive (i.e. WILL BREAK)                                   */
  14.  
  15. /*  dave chapman aug '91  released to public domain                        */
  16.  
  17. char *chouse_n( char *strng, int length);
  18.  
  19. char *chouse_n( char *strng, int length)
  20. {
  21.       static char *str;
  22.       static char *curr;
  23.       static char *pos;       /* for each char in curr(ent string),
  24.                                  its pos in str                            */
  25.       static int  counts[256];
  26.       int i,j;
  27.  
  28.       if (0 >= length)
  29.             return NULL;
  30.  
  31.       if (NULL != strng)
  32.       {
  33.             str = malloc(strlen(strng)); /* first call, prep string for use */
  34.             curr = malloc(2 * length + 1);
  35.             pos = curr + length +1;
  36.  
  37.             for (i = 0; i < 256; counts[i++] = 0)
  38.                   ;
  39.             for (i = 0; strng[i]; i++)
  40.                   counts[strng[i]]++;
  41.  
  42.             for (i = 1, j = 0; i < 256; i++)
  43.             {
  44.                   if (counts[i])
  45.                   {
  46.                         str[j] = i;
  47.                         counts[j++] = counts[i];
  48.                   }
  49.             }
  50.             str[j] = '\0';      /* str is string of distinct chars in order */
  51.                                 /* counts[] holds count of each char        */
  52.  
  53.             /* take first length chars */
  54.  
  55.             for (i = 0,j = 0; i < length; i++)
  56.             {
  57.                   curr[i] = str[j];
  58.                   pos[i] = j;
  59.                   if (!(--counts[j]))
  60.                         j++;
  61.             }
  62.             curr[i] = '\0';
  63.             return curr;
  64.       }
  65.       /* if called with "mississippi",5;
  66.          str -> "imps"
  67.          curr -> "iiiim"
  68.          counts -> 0,0,2,4;
  69.          pos -> 0,0,0,0,1;   */
  70.       
  71.       /* go back to front */
  72.  
  73.       for (j = length; j > 0;)
  74.       {
  75.             counts[ pos[--j]]++;                      /* "replace" char */
  76.  
  77.             /* look for a new char for curr posit. */
  78.  
  79.             for ( i = ++pos[j]; str[i] && ! counts[i]; i++)
  80.                   ;
  81.             if (0 != (curr[j] = str[i]))              /* found a char   */
  82.             {
  83.                   --counts[i];
  84.                   pos[j] = i;
  85.  
  86.                   /* placed char, fill out rest of string  */
  87.  
  88.                   for (++j, i = 0; j < length; j++)
  89.                   {
  90.                         for ( ; !counts[i]; i++)
  91.                               ;
  92.                         curr[j] = str[i];       /* first available char */
  93.                         --counts[i];
  94.                         pos[j] = i;
  95.                   }
  96.                   return curr;
  97.             }
  98.             /* no more chars for this pos ; go back one */
  99.       }
  100.       /*  done */
  101.       return NULL;
  102. }
  103.  
  104. main()
  105. {
  106.       char  *str = "aabbccdd";
  107.       int i,j;
  108.  
  109.       j = 0;
  110.       i =  5;
  111.       puts(chouse_n( str, i));
  112.       while (NULL != (str = chouse_n(NULL, i)))
  113.       {
  114.             ++j;
  115.             printf(" %s  %d\n",str,j);
  116.       }
  117.       return 0;
  118. }
  119.