Combinations and permutations: Difference between revisions

=={{header|Java}}==

The second part of this task implies that the computations are performed in floating point arithmetic. However, the maximum value of a double in Java is 1.7976931348623157E308. Hence, larger computations would overflow. As a result, this task was interpreted so that “using” means “displayed”.

<lang Java>

import java.math.BigInteger;

public class CombinationsAndPermutations {

public static void main(String[] args) {

System.out.println(Double.MAX_VALUE);

System.out.println("A sample of permutations from 1 to 12 with exact Integer arithmetic:");

for ( int n = 1 ; n <= 12 ; n++ ) {

int k = n / 2;

System.out.printf("%d P %d = %s%n", n, k, permutation(n, k));

}

System.out.println();

System.out.println("A sample of combinations from 10 to 60 with exact Integer arithmetic:");

for ( int n = 10 ; n <= 60 ; n += 5 ) {

int k = n / 2;

System.out.printf("%d C %d = %s%n", n, k, combination(n, k));

}

System.out.println();

System.out.println("A sample of permutations from 5 to 15000 displayed in floating point arithmetic:");

System.out.printf("%d P %d = %s%n", 5, 2, permutation(5, 2));

for ( int n = 1000 ; n <= 15000 ; n += 1000 ) {

int k = n / 2;

System.out.printf("%d P %d = %s%n", n, k, display(permutation(n, k), 50));

}

System.out.println();

System.out.println("A sample of combinations from 100 to 1000 displayed in floating point arithmetic:");

for ( int n = 100 ; n <= 1000 ; n += 100 ) {

int k = n / 2;

System.out.printf("%d C %d = %s%n", n, k, display(combination(n, k), 50));

}

}

private static String display(BigInteger val, int precision) {

String s = val.toString();

precision = Math.min(precision, s.length());

StringBuilder sb = new StringBuilder();

sb.append(s.substring(0, 1));

sb.append(".");

sb.append(s.substring(1, precision));

sb.append(" * 10^");

sb.append(s.length()-1);

return sb.toString();

}

public static BigInteger combination(int n, int k) {

// Select value with smallest intermediate results

// combination(n, k) = combination(n, n-k)

if ( n-k < k ) {

k = n-k;

}

BigInteger result = permutation(n, k);

while ( k > 0 ) {

result = result.divide(BigInteger.valueOf(k));

k--;

}

return result;

}

public static BigInteger permutation(int n, int k) {

BigInteger result = BigInteger.ONE;

for ( int i = n ; i >= n-k+1 ; i-- ) {

result = result.multiply(BigInteger.valueOf(i));

}

return result;

}

}

</lang>

{{out}}

<pre>

1.7976931348623157E308

A sample of permutations from 1 to 12 with exact Integer arithmetic:

1 P 0 = 1

2 P 1 = 2

3 P 1 = 3

4 P 2 = 12

5 P 2 = 20

6 P 3 = 120

7 P 3 = 210

8 P 4 = 1680

9 P 4 = 3024

10 P 5 = 30240

11 P 5 = 55440

12 P 6 = 665280

A sample of combinations from 10 to 60 with exact Integer arithmetic:

10 C 5 = 252

15 C 7 = 6435

20 C 10 = 184756

25 C 12 = 5200300

30 C 15 = 155117520

35 C 17 = 4537567650

40 C 20 = 137846528820

45 C 22 = 4116715363800

50 C 25 = 126410606437752

55 C 27 = 3824345300380220

60 C 30 = 118264581564861424

A sample of permutations from 5 to 15000 displayed in floating point arithmetic:

5 P 2 = 20

1000 P 500 = 3.2978863640988537122024252070116261706996485697981 * 10^1433

2000 P 1000 = 8.2415012140674255266380217928953202425839550211348 * 10^3167

3000 P 1500 = 8.6229457673788561572282325050469704818001698192368 * 10^5015

4000 P 2000 = 5.5146268042637929575202252487087217092097210095831 * 10^6937

5000 P 2500 = 2.5959899179479570425022364594725223975158226787173 * 10^8914

6000 P 3000 = 6.4684674799045492726351265543133876130483115297807 * 10^10934

7000 P 3500 = 3.6978393541988590953223392044469547113117500019066 * 10^12991

8000 P 4000 = 2.8347416494109128583587900207169062803923698647730 * 10^15079

9000 P 4500 = 3.5613559022062915735922606191272180393638776777367 * 10^17194

10000 P 5000 = 6.7310091721588924046678115055013992269082753633190 * 10^19333

11000 P 5500 = 7.1714299723894354619599359891785521535675525394493 * 10^21494

12000 P 6000 = 4.4778633072110971517945389774618813158941392935141 * 10^23675

13000 P 6500 = 3.6571405647713639990172807053439865891697112165983 * 10^25874

14000 P 7000 = 1.5680448683572888099973548116924953997328821172933 * 10^28090

15000 P 7500 = 2.2454775022523692436484435950526532351441855443096 * 10^30321

A sample of combinations from 100 to 1000 displayed in floating point arithmetic:

100 C 50 = 1.00891344545564193334812497256 * 10^29

200 C 100 = 9.0548514656103281165404177077484163874504589675413 * 10^58

300 C 150 = 9.3759702772827452793193754439064084879232655700081 * 10^88

400 C 200 = 1.0295250013541443297297588032040198675721092538107 * 10^119

500 C 250 = 1.1674431578827768292093473476217661965923008118031 * 10^149

600 C 300 = 1.3510794199619426851447487797850453039723394544919 * 10^179

700 C 350 = 1.5857433585316795487607022764754299250587342835720 * 10^209

800 C 400 = 1.8804244186835312700958607615195351332156581822914 * 10^239

900 C 450 = 2.2474718820660159573188913903771345843514101350359 * 10^269

1000 C 500 = 2.7028824094543656951561469362597527549615200844654 * 10^299

</pre>