How to do Combinations/Permutations in BlueJ

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

  1. lebaz95

    lebaz95 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?
    lebaz95, Nov 8, 2012
    1. Advertisements

  2. lebaz95

    lebaz95 Guest

    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.
    lebaz95, Nov 8, 2012
    1. Advertisements

  3. lebaz95

    markspace Guest

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

    markspace, Nov 8, 2012
  4. lebaz95

    Eric Sosman Guest

    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, Nov 8, 2012
  5. lebaz95

    Daniel Pitts Guest

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

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

    Eric Sosman Guest

    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

    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, Nov 8, 2012
  7. Tragically hilarious. Hilariously tragic. Or both.


    Gene Wirchenko
    Gene Wirchenko, Nov 8, 2012
  8. lebaz95

    Arne Vajhøj Guest

    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(perm(5, 3));
    System.out.println(comb(5, 3));

    Arne Vajhøj, Nov 8, 2012
  9. lebaz95

    Daniel Pitts Guest

    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
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.