Permutations & Combinations for large inputs

[Dieter]

(05-24-2015 05:39 PM)Dave Britten Wrote:  This program will calculate permutations or combinations (nPr and nCr) for arguments that would normally overflow the FACT function when using the standard forms n!/(n-r)! and n!/(r!(n-r)!). This is a good example of using flag 25 to handle errors. The method employed here is to attempt the standard forms, setting flag 25 before each FACT, then bailing out to a routine that performs repeated multiplication and division if FACT overflowed.

Dave, your method requires just one single overflow test: If n! does not overflow, the smaller values (n–r)! and r! won't either. So lines 17,19 and 20 resp. 25, 27 and 28 can be removed. They should be removed because a set flag 25 may cover other errors, e.g. non-integer or negative arguments.

Just for comparison, here is another version that does not require any data registers and runs faster due to two separate loops and some further improvements within these. For instance two counters are used that are set up before the loops start so that no additional arithmetics within the loops are required. Both loops can be combined to one, but in this case especially nPr would run slower. The program also uses the property Comb(n,r) = Comb(n, n–r), which substantially speeds up the program for r > n/2. Flag 25 is not used – checking whether n>69 will do.

Code:

01 LBL"NPR" // Permutations
02 CF 05
03 GTO 00
04 LBL"NCR" // Combinations
05 SF 05
06 LBL 00
07 x<>y
08 69
09 x<y?     // n>69?
10 GTO 01   // then use iterative method
11 RDN      // else compute result directly
12 FACT     // n!
13 LastX
14 RCL Z
15 -
16 FACT     // (n-r)!
17 /        // nPr = n!/(n-r)!
18 FC?C 05  // Permutations?
19 RTN      // then quit
20 R↑       // else recall r from stack
21 FACT     // r!
22 /        // nCr = nPr / r!
23 RTN
24 LBL 01   // iterative methods start here
25 FS?C 05  // Combinations?
26 GTO 03   // then continue at LBL 03
27 SIGN     // x:=1
28 RCL Z
29 x<>y
30 x>y?     // r < 1 (i.e. = 0)?
31 RTN      // then return 1
32 x<>y
33 RDN
34 LBL 02   // start nPr loop
35 RCL Y    // multiply by n, n-1, n-2, ...
36 *
37 DSE Y    // decrement n
38 LBL 00   // dummy label = NOP
39 DSE Z    // decrement counter
40 GTO 02
41 RTN
42 LBL 03   // prepare nCr loop
43 RDN
44 RCL X
45 RCL Z
46 -
47 LastX
48 x<y?
49 x<>y    // leave min(r, n-r) in y
50 SIGN    // x:=1
51 x>y?    // r resp. n-r < 1 (i.e. = 0)?
52 RTN     // then return 1
53 LBL 04
54 RCL Z   // multiply by n, n-1, n-2, ...
55 *
56 RCL Y   // divide by r, r-1, r-2, ..., 1
57 /
58 DSE Z   // decrement n
59 LBL 00  // dummy label = NOP
60 DSE Y   // decrement r (= counter)
61 GTO 04
62 END

I sincerely hope you do not mind my suggestion – it includes some basic ideas that may be helpful for other programs as well.

Edit: program modified to handle r=0 (and n–r=0 for nCr) correctly.

Dieter