Message from discussion How to do Combinations/Permutations in BlueJ
Received: by 10.66.75.39 with SMTP id z7mr4279744pav.26.1352434466757;
Thu, 08 Nov 2012 20:14:26 -0800 (PST)
From: Daniel Pitts <newsgroup.nos...@virtualinfinity.net>
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:16.0) Gecko/20121026 Thunderbird/16.0.2
Subject: Re: How to do Combinations/Permutations in BlueJ
References: <email@example.com> <firstname.lastname@example.org> <email@example.com> <avQms.8830$J_3.firstname.lastname@example.org> <email@example.com>
NNTP-Posting-Date: Fri, 09 Nov 2012 04:14:25 UTC
Date: Thu, 08 Nov 2012 23:14:24 -0500
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
On 11/8/12 1:18 PM, Eric Sosman wrote:
> On 11/8/2012 10:48 AM, Daniel Pitts wrote:
>> On 11/8/12 9:10 AM, Eric Sosman wrote:
>>> On 11/7/2012 11:53 PM, leba...@gmail.com wrote:
>>>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, leb...@gmail.com
>>>>> I would like to create a program that will do problems like
>>>>> (xa+yb)^z. But I would need to do things like (5!/3!(5-3)!) How would
>>>>> I get this done?
>>>> rslt = 1;
>>>> for(i = e; i > 0; i --)
>>>> rslt *= i;
>>>> I asked my brother and he helped me. e in this program is a user input
>>>> so you may replace it as you see fit.
>>> A warning: If `e' is greater than 12, this calculation will
>>> produce values too large for an `int':
>>> 479001600 = 12!
>>> 2147483647 = Integer.MAX_VALUE
>>> 6227020800 = 13!
>>> You can go somewhat higher by making `rslt' a `long':
>>> 2432902008176640000 = 20!
>>> 9223372036854775807 = Long.MAX_VALUE
>>> 51090942171709440000 = 21!
>>> ... but for anything over 20 even `long' will not suffice. You
>>> should make sure `e' is 20 or smaller (12 or smaller for `int'),
>>> or take a look at the BigInteger class.
>> Or, since you are dividing by factorials, you can factor them out to
>> start with.
>> 5!/3!(5-3)! =
>> 5*4*3*2*1/(3*2*1)(2*1) =
>> (5*4)/(2*1) * (3*2*1)/(3*2*1) =
>> The general formula being n!/r!(n-r)!
> One good way to arrange this is
> n / 1 * (n-1) / 2 * (n-3) / 3 * ... * (n-r+1) / r
> It's easy to see that all the divisions have remainder zero.
>> I believe it is possible to keep the results in the range of integers,
>> if the final result is.
> Let's see: After "times (n-k+1) divided by k" we've calculated
> C(n,k). The next product is C(n,k)*(n-k) before dividing by
> (k+1) knocks it back down, so it looks like the product could be
> somewhat larger than the eventual result, maybe too large. Hmm:
> If we try to calculate C(30,15) this way, we'll get as far as
> C(30,14) = 145422675
> and then multiply by 16
> C(30,14)*16 = 2326762800 > Integer.MAX_VALUE
> and then divide by 15
> C(30,14)*16/15 = C(30,15) = 155117520 < Integer.MAX_VALUE
why would we multiply first? 16 and 15 are coprime, so we can divide
first without changing the integer result.