Post Reply 
(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
(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...
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




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