Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #19653 > unrolled thread

How to do Combinations/Permutations in BlueJ

Back to article view | Back to comp.lang.java.programmer

Contents

  How to do Combinations/Permutations in BlueJ lebaz95@gmail.com - 2012-11-07 18:28 -0800
    Re: How to do Combinations/Permutations in BlueJ lebaz95@gmail.com - 2012-11-07 20:53 -0800
      Re: How to do Combinations/Permutations in BlueJ markspace <-@.> - 2012-11-07 23:03 -0800
        Re: How to do Combinations/Permutations in BlueJ Gene Wirchenko <genew@ocis.net> - 2012-11-08 11:16 -0800
      Re: How to do Combinations/Permutations in BlueJ Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-11-08 09:10 -0500
        Re: How to do Combinations/Permutations in BlueJ Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-11-08 10:48 -0500
          Re: How to do Combinations/Permutations in BlueJ Eric Sosman <esosman@comcast-dot-net.invalid> - 2012-11-08 13:18 -0500
            Re: How to do Combinations/Permutations in BlueJ Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-11-08 23:14 -0500
    Re: How to do Combinations/Permutations in BlueJ Arne Vajhøj <arne@vajhoej.dk> - 2012-11-08 15:52 -0500

#19653 — How to do Combinations/Permutations in BlueJ

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?

[toc] | [next] | [standalone]

#19654

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

[toc] | [prev] | [next] | [standalone]

#19656

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

[toc] | [prev] | [next] | [standalone]

#19669

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

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

[toc] | [prev] | [next] | [standalone]

#19660

On 11/7/2012 11:53 PM, lebaz95@gmail.com wrote:
> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, leb...@gmail.com 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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#19661

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

[toc] | [prev] | [next] | [standalone]

#19666

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, lebaz95@gmail.com wrote:
>>> On Wednesday, November 7, 2012 8:28:19 PM UTC-6, leb...@gmail.com 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
esosman@comcast-dot-net.invalid

[toc] | [prev] | [next] | [standalone]

#19674

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

[toc] | [prev] | [next] | [standalone]

#19670

On 11/7/2012 9:28 PM, lebaz95@gmail.com 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web