Share via

Generating All Partitions Of A Set - Fortran 95 Implementation

  • Article

Note that the following implementation is a faithful reproduction of the NEXEQU algorithm in the book Combinatorial Algorithms For Computers and Calculators by Nijenhuis & Wilf. However, the implementation given in the text has been updated to Fortran 95. 

The following F95 program generates all partitions of a set.

SUBROUTINE NEXEQU(N, NC, P, Q, MTC)

INTEGER, DIMENSION(N) :: P

INTEGER, DIMENSION(N) :: Q

LOGICAL MTC

    IF(MTC) GOTO 20

10  NC=1

    DO 11 I=1,N

11  Q(I)=1

    P(1)=N

60  MTC=NC .NE. N

    RETURN

20  M=N

30  L=Q(M)

    IF(P(L) .NE. 1) GOTO 40

    Q(M)=1

    M=M-1

    GOTO 30

40  NC=NC+M-N

    P(1)=P(1)+N-m

    IF(L .NE. NC) GOTO 50

    NC=NC+1

    P(NC)=0

50  Q(M)=L+1

    P(L)=P(L)-1

    P(L+1)=P(L+1)+1

    GOTO 60

END 

The following is a test program for the above sub-routine.

SUBROUTINE TESTNEXEQU

    INTEGER, DIMENSION(5) :: P

    INTEGER, DIMENSION(5) :: Q

    LOGICAL MTC

    INTEGER L

    INTEGER NC

    L = 1

    DO 10 I = 1, 5

        P(I) = 0

        Q(I) = 0

10  CONTINUE

    MTC = .FALSE.

20  CONTINUE

        CALL NEXEQU (5, NC, P, Q, MTC)

        WRITE(*,"(I2)", advance="no") L

        WRITE(*,"(A)", advance="no") " - "

        DO 40 J = 1, NC

            DO 30 I = 1, 5

                IF (Q(I) .EQ. J) WRITE (*,"(I2), ",advance="no") I

30          CONTINUE

            WRITE(*,"(A)", advance="no") " , "

40      CONTINUE

    PRINT *

    L = L+1

    IF (MTC) GOTO 20

END

A C# implementation of the above algorithm will be published soon.

THe above code is made available in the hope that it will be useful. Microsoft (my employer) neither endorses nor gaurantees nor assumes any liability for this code. Neither do I.