Post Reply 
Permutations & Combinations for large inputs
05-24-2015, 05:39 PM
Post: #1
Permutations & Combinations for large inputs
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.

The loop routine will also perform the appropriate division for COMB as the multiplication is being performed, to allow evaluating COMB for arguments that would still overflow PERM even with this method.

For small inputs, execution time should be relatively quick, but larger values will take longer due to the loop operation. The below example takes 33 seconds on my unmodified 41CV.


Inputs:
y: n
x: r

XEQ PERM, or XEQ COMB

Example:
234 ENTER
78 XEQ ALPHA COMB ALPHA
Result: 2.6795468 63

Uses registers 20 and 21, and flags 05 and 25 (error trap). No modules required.

Code:
01 LBL "PERM"
02 CF 05
03 GTO 00
04 LBL "COMB"
05 SF 05
06 LBL 00
07 STO 21
08 X<>Y
09 STO 20
10 SF 25   //Ignore next error
11 FACT
12 FC?C 25 //Was there an error?
13 GTO 01  //Go to loop routine
14 RCL Y
15 ST- L
16 X<> L
17 SF 25
18 FACT
19 FC?C 25
20 GTO 1
21 /
22 FC? 05
23 RTN
24 RCL Y
25 SF 25
26 FACT
27 FC?C 25
28 GTO 01
29 /
30 RTN
31 LBL 01
32 RCL 20
33 1
34 LBL 02
35 FC? 05 //Permutations?
36 GTO 03 //Skip divide by R21
37 RCL 21
38 /
39 LBL 03
40 RCL Y
41 RCL 21
42 -
43 1
44 +
45 *
46 DSE 21
47 GTO 02
48 RTN
49 END
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Permutations & Combinations for large inputs - Dave Britten - 05-24-2015 05:39 PM



User(s) browsing this thread: 1 Guest(s)