C ALGORITHM 403 COLLECTED ALGORITHMS FROM ACM. C ALGORITHM APPEARED IN COMM. ACM, VOL. 14, NO. 01, C P. 048. SUBROUTINE CIRPI (V, K, X) C THIS SUBROUTINE GENERATES ALL K-TUPLES SUCH THAT..... C A) THE SUM OF THE K ELEMENTS OF THE K-TUPLE IS V, C B) EACH OF THE ELEMENTS IS AN INTEGER GREATER THAN 0, AND C C) NO K-TUPLE IS A CYCLIC PERMUTATION OF ANY OTHER K-TUPLE. C THE K-TUPLE IS STORED IN ARRAY X, WITH ONE ELEMENT C PER ARRAY ELEMENT. EACH K-TUPLE IS PROCESSED BY THE USER C (USING THE SUBROUTINE *PROCES*) BEFORE THE NEXT K-TUPLE IS C GENERATED. THE SUBROUTINE *PROCES* MUST NOT CHANGE THE C CONTENTS OF THE ARRAY X. INTEGER X(K), V, V1, V2, C, SUM V1 = V-K+1 V2 = V/K K1 = K-1 K2 = K-2 SUM = K1 C INITIALIZE THE ARRAY X WITH THE FIRST K-TUPLE. DO 100 I = 1, K1 X(I) = 1 100 CONTINUE GO TO 115 C GENERATE THE NEXT K-TUPLE WHICH SATISFIES THE GIVEN C CONDITIONS, A) - C). 110 C = 1 SUM = X(1) DO 113 I = 1, K2 I1 = K-I X(I1) = X(I1)+C IF(X(I1) .LT. V1) GO TO 111 X(I1) = X(1) GO TO 112 111 C = 0 112 SUM = SUM+X(I1) 113 CONTINUE IF (C .EQ. 0) GO TO 115 X(1) = X(1)+1 IF (X(1) .GT. V2) RETURN DO 114 I1 = 2, K1 X(I1) = X(1) 114 CONTINUE SUM = X(1)*K1 V1 = V-SUM 115 SUM = V-SUM IF (SUM .LT. X(1)) GO TO 110 X(K) = SUM C CHECK TO SEE IF THE K-TUPLE IS A CYCLIC PERMUTATION OF C ANY PREVIOUSLY GENERATED K-TUPLES. IF IT IS, GENERATE THE C NEXT CANDIDATE, OTHERWISE, CALL THE SUBROUTINE *PROCES* TO C PROCESS THE K-TUPLE BEFORE GENERATING THE NEXT ONE. 120 DO 122 I = 2, K IF (X(I) .GT. X(1)) GO TO 122 IF (X(I) .LT. X(1)) GO TO 110 I1 = I+1 DO 121 I2 = 2, K IF (I1 .GT. K) I1 = I1-K IF (X(I1) .GT. X(I2)) GO TO 122 IF(X(I1) .LT. X(I2)) GO TO 110 I1 = I1+1 121 CONTINUE GO TO 130 122 CONTINUE 130 CALL PROCES (X, K) GO TO 110 END