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
    #1
    1. Advertising

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

  3. markspace Guest

    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
    #3
  4. Eric Sosman Guest

    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
    #4
  5. Daniel Pitts Guest

    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
    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. Eric Sosman Guest

    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
    > 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
    d
     
    Eric Sosman, Nov 8, 2012
    #6
  7. 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
    #7
  8. Arne Vajhøj Guest

    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
    #8
  9. Daniel Pitts Guest

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

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

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,117
    Leor Zolman
    Apr 13, 2004
  2. Alex Vinokur
    Replies:
    2
    Views:
    2,795
    Alex Vinokur
    May 13, 2004
  3. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,284
    DHOLLINGSWORTH2
    Mar 11, 2005
  4. IchBin
    Replies:
    0
    Views:
    554
    IchBin
    Jul 29, 2006
  5. Replies:
    6
    Views:
    468
Loading...

Share This Page