2
$\begingroup$

I'm bad at math and hope I explain this right(please don't be upset if I don't, I'm not trying to be lazy or a jerk, I really don't understand what information is sometimes required and focus on the wrong part I think is important).

Basically I have a program that looks for combinations. The best way to explain is it vai an example, say you have 4 items you want to buy at a store: apple,peach,pear and orange. You want to know how much percent you can fit of each into a basket but you tell yourself you want a min. of 20% of each item and a max of 60% of each item(so apple:25%, peach:25%, pear:25%, and orange:25% works perfectly but not apple:0%, peach:0%, pear:50%, and orange:50% because we set a min of 25%).

So my program seems to work and using the above example, I found this code that helps me figure out exactly how many results to expect:

import math  def nCr(n,r):     f = math.factorial     return f(n) / f(r) / f(n-r)  if __name__ == '__main__':     print nCr(20+4-1,20)  #percent+buckets(items)-1, percent 

this gives me the correct answer(1771) because it doesn't need to factor in the max(60%) because its never reached(it only uses 20% as the input). But is there a way I could modify this formula(or use something else) that would tell me how many results to expect if I have something like 40 items with a range of 2-5% or something(something that factors in the max value as well).

Any help would be great..As I mentioned, I'm not good at math so if possible can you explain it as simply as possible?

1 Answers 1

1

This is a form of restricted composition (similar to a partition, but with order mattering), which you can calculate using recurrences. You seem to be assuming exact percentages.

I have a Java applet which does something similar and you can see the code (though it was not designed to be easy to read for anyone else: this particular calculation uses the fifth of the Composition methods).

The applet assumes each part is at least 1, so you would have to recast your problem: the number of compositions of 100 into exactly 4 parts with each part at least 20 and no more than 60 is the same [by taking 19 off each of the 4 parts] as the number of compositions of 24 into exactly 4 positive parts with each part no more than 41. As you say, the answer is 1771.

Similarly the the number of compositions of 100 into exactly 40 parts with each part at least 2 and no more than 5 is the same as the number of compositions of 60 into exactly 40 positive parts with each part no more than 4. The applet gives an answer of 1725325033144622.

  • 0
    Thanks so much Henry, this looks awesome..I understand the postive parts, no more than(is the range)..but what is composition how are you deriving 24 and 60? 24 in my example was min range(20%)-items(4), but in the second example min(2-40 is not 60)..I'm confused. Also are you running the code directly of via the site? its been running 15 minutes for me to test your examples.2012-05-26
  • 0
    come to think about it, if you have the formula it might be easier as I have a function that I can just plug the numbers into..2012-05-26
  • 0
    @Lostsoul: Each time I reduced the minimum to $1$: I took $19$ off each of the $4$ parts and $100-19\times 4 = 24$. In the second case I took $1$ off each of the $40$ parts and $100-1\times 40 = 60$.2012-05-26
  • 0
    Thanks for that Henry. Did you run this on the site you sent me? I have been trying to run the applet but I never get any results. I've tried it with both the latest firefox/chrome(I am using a mac). Is it working for you? and if so how long does it take(I stop it after 10 minutes)?2012-05-29
  • 0
    or better, do you know the formula for this? I think I can program it myself if I can see the logic.2012-05-29
  • 0
    Choosing "Compositions of" 60; "Exact number of terms:" 40; "Each term no more than:" 4; and then clicking on "Calculating partitions" gives me the answer in less than a second in both Firefox and Chrome (on Windows 7).2012-05-29
  • 0
    ahh, your right..I just tried on my windows machine and it works. I'm sorry about, not sure what's wrong with the Mac. The formating looks different though on the mac and on the windows machine, I didn't see that box that displays the answer. Thanks so much Henry..This is awesome!2012-05-29