(PC-12xx~14xx) pnxcb combination generator - Printable Version +- 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=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.