home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / c / 20054 < prev    next >
Encoding:
Internet Message Format  |  1993-01-22  |  3.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!asuvax!ncar!noao!amethyst!organpipe.uug.arizona.edu!news
  2. From: dave@cs.arizona.edu (Dave Schaumann)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Neophyte C programmer needs HELP!
  5. Message-ID: <1993Jan22.040237.9860@organpipe.uug.arizona.edu>
  6. Date: 22 Jan 93 04:02:37 GMT
  7. References: <1993Jan19.122451.10366@ac.dal.ca> <1993Jan19.213452.4531@organpipe.uug.arizona.edu> <1993Jan19.221115.4901@organpipe.uug.arizona.edu> <1993Jan20.044915.12170@Princeton.EDU>
  8. Sender: news@organpipe.uug.arizona.edu
  9. Reply-To: dave@cs.arizona.edu (Dave Schaumann)
  10. Organization: University of Arizona
  11. Lines: 67
  12. In-Reply-To: lhjensen@fish.Princeton.EDU (Leif Jensen)
  13.  
  14. In article <1993Jan20.044915.12170@Princeton.EDU>, lhjensen@fish (Leif Jensen) writes:
  15. The problem:
  16.  
  17. >>>>2.    If Sn denotes the number of subsets of {1,2,3,...,n} that do *not*
  18. >>>>    contain two *consecutive* integers, write an algorithm and program
  19. >>>>    to compute the value Sn for any set {1,2,3,...,n}.  For example:
  20. >>>>    S3=5 since the subsets of {1,2,3} that do not contain consecutive
  21. >>>>    integers are {}, {1}, {2}, {3}, {1,3}.
  22.  
  23. >How would the dynamic programming solution go? (and why would it
  24. >be preferable to an analytic solution?)
  25.  
  26. Let's consider the "analytic" solution, by which I presume you mean the
  27. brute force method.  This is simply
  28.  
  29.   1. Generate all possible subsets.
  30.   2. Count the ones that meet the restriction.
  31.  
  32. Nice and simple.  Unfortunately, there are combinatorially many subsets,
  33. and so this solution is impractical for very large n.
  34.  
  35. Hmm.  After looking at my algorithms book, perhaps "Dynamic programming"
  36. isn't quite the best description of what I had in mind...
  37.  
  38. A typical algorithm to choose m items from n possible choices would be
  39.  
  40. int Chosen[N] ; /* assume all 0 initially */
  41.  
  42. void choose( int last_choice, int num, int max ) {
  43.   int i ;
  44.  
  45.   if( num == 0 ) { check( Chosen ) ; return ; }
  46.  
  47.   for( i = last_choice+1 ; i < max ; i++ ) 
  48.     if( !Chosen[i] ) {
  49.       Chosen[i] = 1 ; choose( i, num-1, max ) ; Chosen[i] = 0 ;
  50.       }
  51.  
  52.   }
  53.  
  54. The problem is that this algorithm generates lots of "impossible"
  55. candidates.  However, if one simply initializes "i" to "last_choice+2"
  56. instead of "last_choice+1", all generated subsets fit the requirement.
  57. Of course, since the number of such subsets increases exponentially,
  58. it is still an exponential algorithm, but it is much better than
  59. the first...
  60.  
  61. Of course, this is not dynamic programming at all.  In my defense, I
  62. can say that I did come to realize this solution by thinking about
  63. a dynamic programming solution.
  64.  
  65. BTW, for those wondering, dynamic programming is a method which
  66. an algorithm that would otherwise have combinatorial time complexity
  67. uses (typically a 2-dimensional) array to hold intermediate results.
  68. Exploiting the fact that the combinatorial nature of the algorithm
  69. results from computing the same functions over and over again, this
  70. "saving of intermediate values" results in a polynomial-time algorithm.
  71.  
  72. Those further interested by my (admittedly weak) description of
  73. dynamic programming are advised to locate a good algorithms book.
  74.  
  75. I see that _Algorithms_ by Sedgewick (and thus, I suppose, it's various
  76. permutations) has a chapter on dynamic programming (although I didn't
  77. see any bibliography of further reading).
  78.  
  79. -- 
  80. Caught an internal error--.brainrc restored
  81.