(12C) Combination and Permutation

[BartDB]

C(n,r) and P(n,r) for HP-12C.

This should work for all cases where the result is less than 1E100.

The C(n,r) routine is based on the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations. In the loop body, the division and multiplication are done alternately to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-12C. Since doing division can result in non-integer results, the final result is rounded to the nearest integer.

The P(n,r) routine is based on the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1).

To use the C(n,r) routine, position the program counter at step 0 if it's not there already, key in n, hit enter, key in r and hit R/S.

To use the P(n,r) routine, position the program counter at step 25 (GTO 25), key in n, hit enter, key in r and hit R/S.

Code:

01  -       ; X=n-r
02  lastx   ; X=r, Y=n-r
03  X<>y    ; for X and Y comparison in next step
04  x<=y    ; would like to use X>Y? test to save previous step, but not available on 12C
05  x<>y    ; place minimum of r and n-r in X 
06  +       ; X=n
07  sto 1   ; Store n in R1
08  lastx   ; X=min(r,n-r)
09  sto 0   ; store in R0. Use as loop counter
10  1       ; Initial value is 1
11  sto 3   ; R3 = result register
12  rcl 0   ; X = loop counter
13  x=0     ; have we reached the end?
14  gto 22  ; if so, then exit
15  sto/ 3  ; update the result
16  rcl 1   ; recall next numerator factor
17  sto* 3  ; update the result
18  1       ;
19  sto- 0  ; decrement loop count
20  sto- 1  ; decrement numerator factor
21  gto 12  ; loop
22  rcl 3   ; place the result on the stack
23  intg    ; take integer 
24  gto 00  ; end

25  x<>y    ; P(n,r) routine. X=n, Y=r 
26  sto 0   ; Store n in R0 
27  x<>y    ; X=r, Y=n 
28  -       ; X=n-r
29  rcl 0   ; X=n, y=n-r 
30  1       ;
31  -       ; subtract 1 from X 
32  x<=y    ; are we done yet? 
33  gto 36  ; if so, then display the result 
34  sto* 0  ; update result 
35  gto 30  ; loop 
36  rcl 0   ; display the result
37  gto 00  ; end

Accuracies (wrong didgits are underlined)

Combinations

\begin{array}{|l|r|r|}
\hline Inputs & HP-12C & Wolfram Alpha \\\hline
15C5 & 3003 & 3003 \\\hline
36C7 & 8347680 & 8347680 \\\hline
90C7 & 747137556\underline{7} & 7471375560 \\\hline
101C6 & 126733992\underline{1} & 1267339920 \\\hline
70C8 & 94403509\underline{38} & 9440350920 \\\hline
425C23 & 5.9872995\underline{10}E37 & 5.987299532821716... E37 \\\hline
200C55 & 7.7183408\underline{23}E49 & 7.718340811430957... E49 \\\hline
335C167 & 3.044358\underline{801}E99 & 3.044358793146979... E99 \\\hline
\end{array}

Permutations

\begin{array}{|l|r|r|}
\hline 25P7 & 2422728000 & 2422728000 \\\hline
99P5 & 8582777280 & 8582777280 \\\hline
100P45 & 7.35060259\underline{4}E84 & 7.350602595423500... E84 \\\hline
5000P27 & 6.94462245\underline{9}E99 & 6.944622452543926... E99 \\\hline
\end{array}

[Gamo]

Hello BartDB

Your program is very good, keep the good work !!


Gamo

[pier4r]

Just giving another comparison (against the sharp el506w with built in functions)

Accuracies (wrong didgits are underlined)

Combinations

\begin{array}{|l|r|r|}
\hline Inputs & HP-12C & \texttt{Sharp el506w} \\\hline
15C5 & 3003 & 3003 \\\hline
36C7 & 8347680 & 8347680 \\\hline
90C7 & 747137556\underline{7} & 7471375560 \\\hline
101C6 & 126733992\underline{1} & 1267339920 \\\hline
70C8 & 94403509\underline{38} & 9440350920 \\\hline
425C23 & 5.9872995\underline{10}E37 & 5.98729953\underline{3}E37 \\\hline
200C55 & 7.7183408\underline{23}E49 & \texttt{error} \\\hline
335C167 & 3.044358\underline{801}E99 & \texttt{error} \\\hline
\end{array}

Permutations

\begin{array}{|l|r|r|}
\hline 25P7 & 2422728000 & 2422728000 \\\hline
99P5 & 8582777280 & 8582777280 \\\hline
100P45 & 7.35060259\underline{4}E84 & 7.350602595E84 \\\hline
5000P27 & 6.94462245\underline{9}E99 & 6.94462245\underline{3}E99 \\\hline
\end{array}

[Gamo]

HP Prime on CAS mode

5000 P 27 result
69446224525439268794572102670318704884478498898385274145791051328237007711099346​99558993920000000000 same result from WolfarmAlpha.

HP Prime calculate just like a real computer computation this is a very capable calculator ever!!!

Gamo

[pier4r]

The hp 50g does the same (and I guess all the math environments with exact computations/big integers , as long as the memory is enough).

[Joe Horn]

(08-18-2017 12:50 PM)pier4r Wrote:  The hp 50g does the same (and I guess all the math environments with exact computations/big integers , as long as the memory is enough).

Actually, both the 50g and Prime have built-in limitations on large integers, in different ways.

The 50g doesn't allow integer exponents greater than 9999 (e.g. 2^9999 works but 2^10000 says "^ Error: Integer too large"). However, the 50g allows the integers themselves to be as big as available memory (as you said), e.g. 2^9999 can be squared without error, and squared again, and so on, until you run out of memory.

Prime however imposes a maximum size on large integers themselves, regardless of available memory. It seems to be 2^8599-1, but I've not seen that documented anywhere. Try this in CAS on your Prime: \[\left ( 2^{8598}-1 \right )\cdot 2+1\]This yields an integer that contains 2589 digits. But now try to add 1 to it, and it yields infinity. So I think that's Prime's largest allowed integer, approximately 3.6E2588.

[pier4r]

Nice info there Joe! Many thanks for sharing!

impressive the 50g though, as I would have expected the prime to show off with all its memory.

[BartDB]

(08-18-2017 08:55 AM)pier4r Wrote:  Just giving another comparison (against the sharp el506w with built in functions)

Accuracies (wrong didgits are underlined)

Hi, I see there are a few error entries. You might be interested in this thread in the old forum:
http://www.hpmuseum.org/cgi-sys/cgiwrap/...ead=173300

[pier4r]

(08-18-2017 04:58 PM)BartDB Wrote:  Hi, I see there are a few error entries. You might be interested in this thread in the old forum:
http://www.hpmuseum.org/cgi-sys/cgiwrap/...ead=173300

Nice find! As users in the thread linked observed I have the 506W not the W506, still the creativity impresses me to abuse the integration function. This are the real calculator users! The ones that know the math/implementation well enough to bent the calculator in many cases to their needs, even when according to the manual there is no other way.

Let's see if I am able to reproduce the steps.

[Dieter]

(08-17-2017 09:49 PM)BartDB Wrote:  The C(n,r) routine is based on the identity C(n,r) = C(n,n-r), selecting the minimum value of r and n-r for the calculations.

That's a good idea that can significantly speed up the calculation. But your program chooses the maximum instead of the minimum. ;-) Swap steps 03 and 04 and the program should work as intended.

(08-17-2017 09:49 PM)BartDB Wrote:  In the loop body, the division and multiplication are done alternately to avoid overflows in cases where the intermediate calculations exceed the dynamic range of the HP-12C. Since doing division can result in non-integer results, the final result is rounded to the nearest integer.

The result is not rounded but truncated. If you want to round you should add a small amount like 0,1 or 0,3 before INTG trims off the decimals.

But you can address the roundoff problem by counting the denominator up instead of down. This yields integer results after each division. On the other hand overflow may occur a little bit earlier, but this can be handled by initializing R3 with 0,001 instead of 1 and finally multiplying the result by 1000.

(08-17-2017 09:49 PM)BartDB Wrote:  The P(n,r) routine is based on the identity P(n,r) = n x (n-1) x (n-2) x ... x (n-r+1).

That's a nice and very compact routine. But does it also return correct results for r=0 ?
Maybe this works better:

Code:

.. ...
25 CHS
26 x<>y
27 +
28 LstX
29 1
30 STO 3
31 R↓
32 x≤y?
33 GTO 22
34 STO*3
35 1
36 -
37 GTO 32

Dieter

[Gamo]

Combination and Permutation program for HP-12C

--------------------------------------------------------

For Combination assuming that user already know that

mCo = mCm = 1
mC1 = m

For Permutation assuming tha user already know that

mPo = 1
mP1 = m
mPm = m!
--------------------------------------------------------
Formula used:

C(m,n) = [m x (m-1) x (m-2) x ... x (m-n+1)] ÷ (1 x 2 x 3 x ... x n)

P(m,n) = m x (m-1) x (m-2) x ... x (m-n+1)
--------------------------------------------------------

Program:

Code:


01 ENTER
02 STO 0 
03 R/S
04 STO 1
05  1
06  -
07  1
08  +
09  -
10  1
11  +
12  x
13 LSTx
14 RCL 0
15  1
16  -
17 X≤Y
18 GTO 21
19 R↓
20 GTO 10
21 R↓
22 R↓
23 ENTER
24 RCL 1
25  n!
26  ÷
27 GTO 00

------------------------------------------------
Remark: For 2 ≤ n

Example: [FIX] 0
80C5 and 80P5

80 [R/S] display 80
5 [R/S] display Combination 24,040,016
[X<>Y] display Permutation 2,884,801,920
-------------------------------------------------
Gamo 3/2020