How to do Combinations/Permutations in BlueJ

[lebaz95]

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?

 

[lebaz95]

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.

 

[markspace]

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>

 

[Eric Sosman]

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.

 

[Daniel Pitts]

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

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

 

[Eric Sosman]

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

 

[Gene Wirchenko]

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

 

[Arne Vajhøj]

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

 

[Daniel Pitts]

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.


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.