(PC-12xx~14xx) pnxcb combination generator
03-31-2021, 12:41 AM (This post was last modified: 03-31-2021 08:42 PM by robve.)
Post: #1
 robve Senior Member Posts: 404 Joined: Sep 2020
(PC-12xx~14xx) pnxcb combination generator
PNXCB COMBINATION GENERATOR
For SHARP PC-12xx to 14xx

Credit: ALG. PNXCB https://dl.acm.org/doi/pdf/10.1145/355826.355830

258 bytes BASIC image (PC-1350)

PNXCB(P,N,K,X,Y) cycles through array of "pointers" P(1..K) to N "items".
- First initialize P to a list of K distinct "pointers" (indices) to N items.
- Then call PNXCB $$n \choose k$$ times to generate all combinations of K items.
- If initially all P(I)=I, then $$n \choose k$$ cycle is complete when P(K)=K.
- Also returns X and Y updated "pointers" in P, which may be useful.

Example: find Pythagorian triples up to 40: (x,y,z) such that x2 + y2 = z2
10 N=40,K=3: DIM P(K): P(1)=1,P(2)=2,P(3)=3
20 IF P(1)*P(1)+P(2)*P(2)=P(3)*P(3) PRINT P(1);P(2);P(3)
30 GOSUB "PNXCB"
40 IF P(K)<>K GOTO 20
50 END
RUN
3. 4. 5.
6. 8. 10.
5. 12. 13.
9. 12. 15.
8. 15. 17.
12. 16. 20.
7. 24. 25.
15. 20. 25.
10. 24. 26.
20. 21. 29.
18. 24. 30.
16. 30. 34.
21. 28. 35.
12. 35. 37.
15. 36. 39.
24. 32. 40.

Example: find all pairs of distinct prime numbers p and q up to 97 such that p + q = 100
10 N=25,K=2: DIM P(K),R(N): RESTORE
20 FOR I=1 TO K: P(I)=I: NEXT I
30 FOR I=1 TO N: READ R(I): NEXT I
40 DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
50 P=R(P(1)),Q=R(P(2)): IF P+Q=100 PRINT P,Q
60 GOSUB "PNXCB"
70 IF P(K)<>K GOTO 50
80 END
RUN
3. 97.
11. 89.
17. 83.
29. 71.
41. 59.
47. 53.

Code:
' PNXCB COMBINATION GENERATOR ' For SHARP PC-12xx to 14xx by Robert van Engelen ' Credit: '   https://dl.acm.org/doi/pdf/10.1145/355826.355830 ' ' PNXCB(P,N,K,X,Y) cycles through array of "pointers" P(1..K) to N "items". ' First initialize P to a list of K distinct "pointers" (indices) to N items. ' Then call PNXCB NCR(N,K) times to generate all combinations of K items. ' If initially all P(I)=I, then NCR(N,K) cycle is complete when P(K)=K. ' Also returns X and Y updated "pointers" in P, which may be useful. ' ' Example: '   Find Pythagorian triples up to 40: (x,y,z) such that x^2 + y^2 = z^2 '     10 N=40,K=3: DIM P(K): P(1)=1,P(2)=2,P(3)=3 '     20 IF P(1)*P(1)+P(2)*P(2)=P(3)*P(3) PRINT P(1);P(2);P(3) '     30 GOSUB "PNXCB" '     40 IF P(K)<>K GOTO 20 '     50 END '   Find all pairs of distinct prime numbers p and q up to 97 such that p + q = 100 '     10 N=25,K=2: DIM P(K),R(N): RESTORE '     20 FOR I=1 TO K: P(I)=I: NEXT I '     30 FOR I=1 TO N: READ R(I): NEXT I '     40 DATA 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 '     50 P=R(P(1)),Q=R(P(2)): IF P+Q=100 PRINT P,Q '     60 GOSUB "PNXCB" '     70 IF P(K)<>K GOTO 50 '     80 END ' Algorithm: '   void pnxcb(int p[]/*p[0..k-1]*/, int n, int k, int *x, int *y) { '     int j = 1; '     while (1) { '       *x = p[j-1]; '       *y = *x+1; '       if (j == k) { '         if (*y > n) { '           *y = k; '           p[j-1] = *y; '           return; '         } '         p[j-1] = *y; '         if (j > 1) { '           p[j-2] = *x; '           *x = j-1; '         } '         return; '       } '       if (*y < p[j]) { '         p[j-1] = *y; '         if (j > 1) { '           p[j-2] = *x; '           *x = j-1; '         } '         return; '       } '       ++j; '       *x = p[j-1]; '       *y = *x-1; '       if (*y >= j) { '         p[j-1] = *y; '         if (j > 1) { '           *y = j-1; '           p[j-2] = *y; '         } '         return; '       } '       if (j == k) { '         *y = n; '         p[j-1] = *y; '         return; '       } '       ++j; '     } '   } ' VARIABLES '  P(1..K) array of pointers (distinct integers between 1 and N) '  N       number of items to choose from '  K       number of distinct items to choose '  X       old pointer removed from P() '  Y       new pointer added to P() '  J       scratch ' PNXCB(P,N,K,X,Y) -> P, X (old), Y (new), changes J 100 "PNXCB" J=1: REM GOTO 180 FOR DOWN-UP SEQUENCE ' main loop 110 X=P(J),Y=X+1 120 IF J<>K GOTO 160 130 IF Y>N LET Y=K,P(J)=Y: RETURN ' branch 1 140 P(J)=Y: IF J>1 LET P(J-1)=X,X=J-1 150 RETURN ' branch 2 160 IF Y<P(J+1) GOTO 140 170 J=J+1 180 X=P(J),Y=X-1 190 IF Y>=J GOTO 230 200 IF J=K LET Y=N,P(J)=Y: RETURN 210 J=J+1 220 GOTO 110 ' branch 3 230 P(J)=Y: IF J>1 LET Y=J-1,P(J-1)=Y 240 RETURN

Edit: fixed typo + display example program output.

"I count on old friends" -- HP 71B,Prime|Ti VOY200,Nspire CXII CAS|Casio fx-CG50...|Sharp PC-G850,E500,2500,1500,14xx,13xx,12xx...
 « Next Oldest | Next Newest »