/***************************************************************************/
/* */
/* ACM ALGORITHM 466: Four Combinatorial Algorithms */
/* */
/* Gideon Ehrlich, Department of Applied Mathematics, */
/* Weizmann Institute of Science, Rehovot, Israel. */
/* 25 August 1971, 4 Jan. 1972, 12 Dec. 1972. */
/* */
/***************************************************************************/
/* Status 23 October 2007. Transcribed, compiled, but not tested. */
FIRSTPER: PROCEDURE (X, DONE);
DECLARE (X(*), (XN, XX) STATIC) DECIMAL, DONE BIT (1),
(N, S, V, M, L, I, DI, IPI) BINARY STATIC,
(P(0:DIM(X)), IP(DIM(X)-1), D(DIM(X)-1), T(DIM(X))) BINARY CONTROLLED;
N = DIM(X, 1);
IF ALLOCATION (P) THEN FREE P, IP, D, T;
ALLOCATE P, IP, D, T;
DO M = 1 TO N-1; P(M), IP(M) = M; D(M) = -1; END;
XN = X(N); V = -1; S, P(0), P(N) = N; M, L = 1;
T(N) = N-1; T(N-1) = -2; T(2) = 2;
DONE = '0'B;
PERMU: ENTRY (X, DONE);
N = DIM(X);
IF S ^= M THEN DO; X(S) = X(S+V); S = S + V; X(S) = XN; RETURN; END;
I = T(N); DI = D(I);
IP(I), IPI = IP(I) + DI; M = P(IPI); IP(M) = IPI - DI;
P(IPI-DI) = M; P(IPI) = I; M =- IPI + L;
XX = X(M); X(M) = X(M-DI); X(M-DI) = XX;
L = 1 - L; V = -V;
IF P(IPI+DI) < I THEN
DO;
IF I = N-1 THEN RETURN;
T(N) = N-1; T(N-1) = -I; RETURN;
END;
D(I) = -DI;
IF T(I) < 0 THEN
DO; IF T(I) ^= 1-I THEN T(I-1) = T(I); T(I) = I - 1; END;
IF I ^= N-1 THEN DO; T(N) = N-1; T(N-1) = -I - 1; END;
T(I+1) = T(I);
IF I = 2 & P(2) = 2 THEN DONE = '1'B;
END FIRSTPER;
COMBI: PROCEDURE (A, N, X, Y, T, F, I, L, Z, H, C);
DECLARE A(*) BIT(1), (N, X, Y, T(*), F(*), I, L, Z, H(*), C(*)) FIXED;
IF T(I) < 0 THEN
DO; IF -T(I) ^= I-1 THEN T(I-1) = T(I); T(I) = I-1; END;
IF ^A(I) THEN
DO;
X = I; Y = F(L);
IF A(I-1) THEN
F(I) = F(I) - 1;
ELSE
F(I) = I;
IF F(L) = L THEN
DO; L = I; I = T(I); GO TO CHANGE; END;
IF L = N THEN
DO;
T(F(N)) = -I-1; T(I+1) = T(I); I = F(N);
F(N) = F(N) + 1; GO TO CHANGE;
END;
T(L) = -I-1; T(I+1) = T(I);
F(L) = F(L) + 1; I = L; GO TO CHANGE;
END;
Y = I;
IF I ^= L THEN
DO;
F(L),X = F(L) - 1; F(I-1) = F(I);
IF L = N THEN
DO;
IF I = F(N)-1 THEN
DO; I = T(I); GO TO CHANGE; END;
T(F(N)-1) = -I-1; T(I+1) = T(I);
I = F(N) - 1; GO TO CHANGE;
END;
T(L) = -I-1; T(I+1) = T(I); I = L; GO TO CHANGE;
END;
X = N; F(L-1) = F(L); F(N) = N; L = N;
IF I = N-1 THEN DO; I = T(N-1); GO TO CHANGE; END;
T(N-1) = -I-1; T(I+1) = T(I); I = N - 1;
CHANGE:
A(X) = '1'B; A(Y) = '0'B;
H(X),Z = H(Y); C(Z) = X;
END COMBI;
COMPOMIN: PROCEDURE (INDEX, A, N, X, Y, T, F, I, L, Z, H, C);
DECLARE A(*) BIT(1),
(INDEX(*), N, X, Y, T(*), F(*), I, L, Z, H(*), C(*)) FIXED;
CALL COMBI (A, N, X, Y, T, F, I, L, Z, H, C);
INDEX(Z) = INDEX(Z) + X - Y;
INDEX(Z+1) = INDEX(Z+1) + Y - X;
END COMPOMIN;
COMPOMAX: PROCEDURE (INDEX, A, N, X, Y, T, F, I, L, Z, H, C);
DECLARE A(*) BIT(1),
(INDEX(*), N, X, Y, T(*), F(*), I, L, Z, H(*), C(*)) FIXED;
CALL COMBI (A, N, X, Y, T, F, I, L, Z, H, C);
INDEX(Z) = INDEX(Z) - X + Y;
INDEX(Z+1) = INDEX(Z+1) - Y + X;
END COMPOMAX;