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
    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