Received: by 10.66.75.39 with SMTP id z7mr4279744pav.26.1352434466757;
        Thu, 08 Nov 2012 20:14:26 -0800 (PST)
Path: 6ni69118pbd.1!nntp.google.com!npeer03.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!post01.iad.highwinds-media.com!newsfe25.iad.POSTED!not-for-mail
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
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: How to do Combinations/Permutations in BlueJ
References: <9b534783-eb45-458d-8abb-a4c890553971@googlegroups.com> <8d95d877-c3c3-4d36-97f2-389424fdfc43@googlegroups.com> <k7gefs$bp8$1@dont-email.me> <avQms.8830$J_3.6717@newsfe07.iad> <k7gt0s$c5s$1@dont-email.me>
In-Reply-To: <k7gt0s$c5s$1@dont-email.me>
Lines: 74
Message-ID: <Bq%ms.28087$2Q3.21779@newsfe25.iad>
X-Complaints-To: abuse@newsrazor.net
NNTP-Posting-Date: Fri, 09 Nov 2012 04:14:25 UTC
Date: Thu, 08 Nov 2012 23:14:24 -0500
X-Received-Bytes: 3453
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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
>>>> wrote:
>>>>> 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) =
>>    5*4/2
>>
>> 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.