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

  3. lebaz95

    markspace Guest


    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
    #3
  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
    #4
  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) =
    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
    #5
  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
    #6
  7. Tragically hilarious. Hilariously tragic. Or both.

    Sincerely,

    Gene Wirchenko
     
    Gene Wirchenko, Nov 8, 2012
    #7
  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(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
    #8
  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
    #9
    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.