home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / sys / ibm / pc / misc / 14936 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  1.8 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!uwm.edu!biosci!agate!linus!philabs!ehf
  2. From: ehf@philabs.philips.com (Eberhard Fisch)
  3. Newsgroups: comp.sys.ibm.pc.misc
  4. Subject: Re: 'All Possible Combinations' Algorithm
  5. Message-ID: <1992Nov23.222613.12411@philabs.philips.com>
  6. Date: 23 Nov 92 22:26:13 GMT
  7. References: <921123105513@AltaHopa.ftp.com> <1992Nov23.164311.27333@leland.Stanford.EDU>
  8. Sender: news@philabs.philips.com (Mr. C. News)
  9. Reply-To: ehf@philabs.philips.com (Eberhard Fisch)
  10. Organization: Philips Laboratories, Briarcliff, NY 10510
  11. Lines: 33
  12. Originator: ehf@oscar
  13.  
  14.  
  15. In article <1992Nov23.164311.27333@leland.Stanford.EDU>, spagiola@frinext.stanford.edu (Stefano Pagiola) writes:
  16. |> William W. Plummer writes
  17. |> >> Can someone provide me with an algorithm suitable for writing
  18. |> >> a program to dump all possible combinations of 'n' elements
  19. |> >> taken 'm' at a time?
  20. |> > 
  21. |> > n!/(m! * (n-m)!)
  22. |> > 
  23. |> > For instance in the MA Megabucks with 6 numbers out of 36 we have
  24. |> > 
  25. |> > 36!(6! * 30!)  =  36*35*34*33*32*31/(6*5*4*3*2*1)
  26. |> >         = 6*7*34*11*4*31
  27. |> >         = 1,947,792
  28. |> 
  29.  
  30. |> Methinks the original poster wanted to _list_ all possible  
  31. |> combinations, not just calculate how many there are...
  32. |> 
  33. I think your right. Let b(n,m)=n!/m!(n-m)!. 
  34. Here's an informal description of a recursive solution:
  35.  
  36. 1. If m=0 print nothing (empty set) and return.
  37. 2. If m = n print a list of all n elements and return. (this step is not needed
  38.    but prevents a lot of extra function calls.)
  39. 3. If 0 < m < n do the following:
  40.     a) Print all b(n-1,m-1) lists of m elements all
  41.        containing the n-th element.
  42.     b) Print all b(n-1,m) lists of m elements NOT containing the n-th
  43.        element.
  44.     c) return
  45.  
  46. This algorithm comes from the recursion formula: b(n,m)=b(n-1,m-1)+b(n-1,m).
  47.