home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10648 < prev    next >
Encoding:
Text File  |  1992-08-27  |  1.5 KB  |  44 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!caen!takriti
  3. From: takriti@engin.umich.edu (samer Takriti)
  4. Subject: Re: Combinatorial Problem
  5. Message-ID: <Skj-ga#@engin.umich.edu>
  6. Date: Thu, 27 Aug 92 16:16:53 EDT
  7. Organization: University of Michigan Engineering, Ann Arbor
  8. References: <1992Aug27.135518.8048@rhrk.uni-kl.de>
  9. Followup-To: I have a Problem, which I think is very easy
  10. Keywords: combinatorics
  11. Nntp-Posting-Host: maize.engin.umich.edu
  12. Lines: 30
  13.  
  14. I will restate your problem first:
  15. Find the integers x(i), i=1, ..., m
  16. such that
  17. x(1) + x(2) + ... + x(m) = K
  18. l(i) <= x(i) <= u(i), i=1, ..., m
  19.  
  20. I don't think that you can compute the exact number of feasible
  21. solutions. You may obtain some bounds on the number of possible
  22. solutions though.
  23. If you need to exhaust all the solutions you may want to do the 
  24. following:
  25. Create m for loops as follows:
  26. for (x(1)=l(1); x(1)<=K && x(1)<=u(1); x(1)++)
  27.  for (x(2)=l(2); x(2)<=K-x(1) && x(2)<=u(2); x(2)++)
  28.   for (x(3)=l(3); x(3)<=K-x(1)-x(2) && x(3)<=u(3); x(3)++)
  29.    ..........
  30.     for (x(m-1)=l(m-1); x(m-1)<=K-x(1)-x(2)-...-x(m-2) && x(m-1)<=u(m-1); x(m-1)++)
  31.      {
  32.      x(m) = K - x(1) - x(2) - x(3) - ... - x(m-1)
  33.      if x(m) <= u(m)
  34.         printf ("%....", x(1), x(2), ..., x(m))
  35.      }
  36. As you see, the previous code or algorithm gives an upper bound 
  37. on the number of the possible solutions.
  38. If you want to implement this algorithm on a computer, there is 
  39. no need for m-1 loops. You can use recursion.
  40.  
  41. If you are interested in one solution only, you can use integer
  42. programming to do so.
  43. -Samer
  44.