+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not remotely HP Calculators (/forum-9.html)
+--- Thread: (PC-12xx~14xx) pnxcb combination generator (/thread-16569.html)
(PC-12xx~14xx) pnxcb combination generator - robve - 03-31-2021 12:41 AM
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 RETURNEdit: fixed typo + display example program output.