Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #19666

Re: How to do Combinations/Permutations in BlueJ

Show all headers | View raw

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, lebaz95@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

So although we're much better off than by dividing factorials,
caution is still needed.  (This is also a reason to begin by
setting `r = Math.min(r,n-r)': Not only does it make for fewer
iterations, but it helps avoid the central area where the numbers
get big.  C(30,2) = C(30,28) mathematically, but 30/1*29/2 won't
get into trouble while 30/1*29/2*...*3/28 will.)

-- 
Eric Sosman
esosman@comcast-dot-net.invalid

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

How to do Combinations/Permutations in BlueJ lebaz95@gmail.com - 2012-11-07 18:28 -0800
  Re: How to do Combinations/Permutations in BlueJ lebaz95@gmail.com - 2012-11-07 20:53 -0800
    Re: How to do Combinations/Permutations in BlueJ markspace <-@.> - 2012-11-07 23:03 -0800
      Re: How to do Combinations/Permutations in BlueJ Gene Wirchenko <genew@ocis.net> - 2012-11-08 11:16 -0800
    Re: How to do Combinations/Permutations in BlueJ Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-11-08 09:10 -0500
      Re: How to do Combinations/Permutations in BlueJ Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-11-08 10:48 -0500
        Re: How to do Combinations/Permutations in BlueJ Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-11-08 13:18 -0500
          Re: How to do Combinations/Permutations in BlueJ Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-11-08 23:14 -0500
  Re: How to do Combinations/Permutations in BlueJ Arne Vajhøj <arne@vajhoej.dk> - 2012-11-08 15:52 -0500

csiph-web