home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / os / msdos / apps / 5650 < prev    next >
Encoding:
Text File  |  1992-11-23  |  1.6 KB  |  58 lines
  1. Newsgroups: comp.os.msdos.apps
  2. Path: sparky!uunet!spool.mu.edu!darwin.sura.net!Sirius.dfn.de!chx400!news.unige.ch!ugsc2a!fisher
  3. From: fisher@sc2a.unige.ch
  4. Subject: Re: 'All Possible Combinations' Algorithms
  5. Message-ID: <1992Nov23.130227.1@sc2a.unige.ch>
  6. Lines: 46
  7. Sender: usenet@news.unige.ch
  8. Organization: University of Geneva, Switzerland
  9. References: <By0wH5.D3L@apollo.hp.com>
  10. Date: Mon, 23 Nov 1992 11:02:27 GMT
  11.  
  12. In article <By0wH5.D3L@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.  
  16. Wrong group, but here it goes (in somewhat portable c):
  17.  
  18. #include <stdlib.h>
  19. #include <stdio.h>
  20.  
  21. #define swapc(a,b) do {char tmp=(a); (a)=(b); (b)=tmp;} while(0)
  22.  
  23. unsigned choose (unsigned n, char *s, unsigned p, unsigned nb)
  24. /* Select every possible combination of n chars out of s, printing them. */
  25. /* warning: n must be <= strlen(s) !!! */
  26. {
  27.     char *c;
  28.  
  29.     if (n == 0)
  30.     /* enough characters choosen, so print (incrementing nb) */
  31.         printf("%5d: %.*s\n", ++nb, p, s);
  32.     else
  33.     /* select every possible next char and recurse */
  34.         for (c = (s+p);  *c;  c++) {
  35.             swapc(*c, s[p]);
  36.             nb = choose(n-1, s, p+1, nb);
  37.             swapc(*c, s[p]);
  38.             }
  39.     return nb;
  40. }
  41. /* simply call as: */
  42. #define combine(n,s) choose(n,s,0,0)
  43.  
  44. void main(int argc, char *argv[])
  45. {
  46.     if (argc<3) {
  47.         printf("Usage %s <nb> <string>\n", argv[0]);
  48.         printf("Prints all combinations of <nb> chars out of <string>\n");
  49.         }
  50.     else
  51.         combine (atoi(argv[1]), argv[2]);
  52. }
  53.  
  54.  
  55. Good luck,
  56.  
  57. Markus Fischer    Dpt of Anthropology, Geneva CH    fisher@sc2a.unige.ch
  58.