# How to do Combinations/Permutations in BlueJ

Discussion in 'Java' started by lebaz95@gmail.com, Nov 8, 2012.

1. ### Guest

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?

, Nov 8, 2012

2. ### Guest

On Wednesday, November 7, 2012 8:28:19 PM UTC-6, 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.

, Nov 8, 2012

3. ### markspaceGuest

On 11/7/2012 8:53 PM, wrote:
> On Wednesday, November 7, 2012 8:28:19 PM UTC-6,
> 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.

In the real world, people call this a factorial. Here's a fun article
on the subject:

<http://chaosinmotion.com/blog/?p=622>

markspace, Nov 8, 2012
4. ### Eric SosmanGuest

On 11/7/2012 11:53 PM, wrote:
> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, 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.

--
Eric Sosman
d

Eric Sosman, Nov 8, 2012
5. ### Daniel PittsGuest

On 11/8/12 9:10 AM, Eric Sosman wrote:
> On 11/7/2012 11:53 PM, wrote:
>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, 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

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

I believe it is possible to keep the results in the range of integers,
if the final result is.

Daniel Pitts, Nov 8, 2012
6. ### Eric SosmanGuest

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, wrote:
>>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, 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
>
> 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
d

Eric Sosman, Nov 8, 2012
7. ### Gene WirchenkoGuest

On Wed, 07 Nov 2012 23:03:17 -0800, markspace <-@.> wrote:

>On 11/7/2012 8:53 PM, wrote:
>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6,
>> 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.

>In the real world, people call this a factorial. Here's a fun article
>on the subject:
>
><http://chaosinmotion.com/blog/?p=622>

Tragically hilarious. Hilariously tragic. Or both.

Sincerely,

Gene Wirchenko

Gene Wirchenko, Nov 8, 2012
8. ### Arne VajhøjGuest

On 11/7/2012 9:28 PM, 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?

That can be done in many ways.

Here is one:

import java.math.BigInteger;

public class Stat {
private static BigInteger prod(int first, int last) {
BigInteger res = BigInteger.valueOf(first);
for(int i = first + 1; i <= last; i++) {
res = res.multiply(BigInteger.valueOf(i));
}
return res;
}
private static BigInteger prod(int last) {
return prod(1, last);
}
public static BigInteger perm(int n, int p)
{
//return prod(n).divide(prod(n-p));
return prod(n-p+1,n);
}
public static BigInteger comb(int n, int p)
{
return perm(n,p).divide(prod(p));
}
public static void main(String[] args) {
System.out.println(prod(3));
System.out.println(prod(5));
System.out.println(prod(4,5));
System.out.println(perm(5, 3));
System.out.println(comb(5, 3));
}
}

Arne

Arne Vajhøj, Nov 8, 2012
9. ### Daniel PittsGuest

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, wrote:
>>>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6,
>>>> 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
>>
>> 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.

Daniel Pitts, Nov 9, 2012