home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / os / msdos / programm / 10844 < prev    next >
Encoding:
Text File  |  1992-11-22  |  2.4 KB  |  94 lines
  1. Path: sparky!uunet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.os.msdos.programmer
  4. Subject: Re: 'All Possible Combinations' Algorithm
  5. Keywords: combinations
  6. Message-ID: <3907@dozo.and.nl>
  7. Date: 22 Nov 92 13:07:40 GMT
  8. References: <By109I.HEt@apollo.hp.com>
  9. Organization: AND Software BV Rotterdam
  10. Lines: 82
  11.  
  12. In article <By109I.HEt@apollo.hp.com> holbrook@apollo.HP.COM (Alan R. Holbrook) writes:
  13. |Can someone provide me with an algorithm suitable for writing a program
  14. |to dump all possible combinations of 'n' elements taken 'm' at a time?
  15. |That is, given the string 'abcdefghijklmnop', I'd like to be able to produce
  16. |all possible combinations of, say, 'abcde', then of 'abcdf', or of 'cfilnop'
  17. |then 'aceghilmp', etc.  I think you get the idea.
  18.  
  19. Nice little problem ... ok, here's my (naive) solution, enjoy.
  20.  
  21. kind regards,
  22.  
  23. Jos aka jos@and.nl
  24.  
  25. -----8<-----snip----------snip----------snip----------snip----------snip-----
  26. #include <stdio.h>
  27.  
  28. #define MAXP 100        /* Any arbitrary value ... */
  29. #define FREE 1            /* Number not used yet */
  30. #define LOCK 0            /* Number used in a prev position */    
  31.  
  32. int permtab[MAXP];        /* Current permutation */
  33. int locktab[MAXP];        /* Number (not) used table */
  34.  
  35. void perm(n, k)
  36. int n, k;
  37. {
  38.     int i, j;
  39.  
  40.     for (i= 0; i < k; i++) {    /* Init first permutaion */
  41.         permtab[i]= i;
  42.         locktab[i]= LOCK;
  43.     }
  44.  
  45.     for (i= k; i < n; i++)        /* [k ... n-1] are still free */
  46.         locktab[i]= FREE;
  47.  
  48.  
  49.     while (i >= 0) {
  50.     /* 
  51.      * Simply print out the current permutation (n, k)
  52.      */
  53.         for (i= 0; i < k; i++)
  54.             printf("%4d ", permtab[i]);
  55.         printf("\n");
  56.  
  57.     /*
  58.      * Find the rightmost position that can still be incremented,
  59.      * e.g. in (4,3) and the current permutation 124, we have to
  60.      * backup to the second position.
  61.      */
  62.         for (i= k-1; i>= 0; i--) {
  63.  
  64.             locktab[permtab[i]]= FREE;
  65.  
  66.             for (j= permtab[i]+1; j < n; j++)
  67.                 if (locktab[j] == FREE) {
  68.                     locktab[j]= LOCK;
  69.                     permtab[i]= j;
  70.                     break;
  71.                 }
  72.             if (j < n)
  73.                 break;
  74.         }
  75.     /*
  76.      * We found a rightmost position, now fill in
  77.      * all positions to the right of this one,
  78.      * e.g. 124 turned into 13x, we just have to
  79.      * find an unused number for x.
  80.      * If we didn't find a rightmost position in
  81.      * the previous loop, we're done.
  82.      */
  83.         if (i >= 0) 
  84.             for (i++; i < k; i++) 
  85.                 for (j= 0; j < n; j++)
  86.                     if (locktab[j] == FREE) {
  87.                         permtab[i]= j;
  88.                         locktab[j]= LOCK;
  89.                         break;
  90.                     }
  91.     }
  92. }
  93. -----8<-----snip----------snip----------snip----------snip----------snip-----
  94.