V202: Permutations and Combinations

Author(s): F. Beck, T. Lindelöf	Library: MATHLIB
Submitter: K.S. Kölbig	Submitted: 15.09.1978
Language: Fortran	Revised: 07.06.1992

Successive calls to subroutine subprogram PERMU will generate all permutations of a set of integers of total length N consisting of repetitions of the integer 1, followed by repetitions of the integer etc, concluding with repetitions of the integer m, where .

Subroutine subprogram PERMUT generates directly a single member of the set of all lexicographically ordered permutations of the first integers , as specified by its lexicographical ordinal.

Successive calls to subroutine subprogram COMBI will generate all the possible combinations without repetition of integers from the set .

Structure:

SUBROUTINE subprogram
User Entry Names: PERMU, PERMUT, COMBI
Files Referenced: Unit 6

Usage:

Subroutine PERMU:

    CALL PERMU(IA,N)

IA

(INTEGER) One-dimensional array of length . On entry, , must contain the initial set of integers to be permuted (see Examples). A call with will place the set in IA. On exit, IA contains the "next" permutation. If all the permutations have been generated, the next call sets .

N

(INTEGER) Length of the set to be permuted.

Subroutine PERMUT:

    CALL PERMUT(NLX,N,IP)

NLX

(INTEGER) Lexicographical ordinal of the permutation desired.

N

(INTEGER) Length of the set to be permuted.

IP

(INTEGER) One-dimensional array of length . On exit, , contains the NLX-th lexicographically ordered permutation of the integers (see Examples).

Subroutine COMBI:

    CALL COMBI(IC,N,J)

IC

(INTEGER) One-dimensional array of length . The first call must be made with . This generates the first combination . Each successive call generates a new combination and places it in the first J elements of IC. If all the combinations have been generated, the next call sets .

N

(INTEGER) Length of the set from which the combinations are taken.

J

(INTEGER) Length of the combinations.

Examples:

1. Consider the following set of N=12 objects, only 8 are different:

   

   This set consists of m=8 sequences of length , , . Thus, in order to get the possible permutations, set

   

   before calling PERMU(IA,12) the first time.

2. To generate all permutations of N indistinguishable objects, set , which is equivalent to , before calling PERMU(IA,N) the first time.
3. To compute the, lexicographically second, third and last (4!=24) permutions of the set :
   

   CALL PERMUT( 2,4,IP) sets

   CALL PERMUT( 3,4,IP) sets

   CALL PERMUT(24,4,IP) sets

4. To generate and print all 20 combinations of 3 integers from the set one could write:

       ...
       IA(1)=0
     1 CALL COMBI(IC,6,3)
       IF(IC(1) .NE. 0) THEN
        PRINT *, IC(1),IC(2),IC(3)
        GO TO 1
       ENDIF
       ...

Restrictions:

PERMUT: .
COMBI: .

Error handling:

If any of the above conditions is not satisfied, a message is written on Unit 6.

Notes:

1. If or , the subprograms return control without action.
2. The number of distinct permutations of a set of N numbers which can be decomposed into m groups of indistinguishable elements is given by

   

   where . This number can become large even for seemingly simple cases, e.g. in Example 1 above,