V202 Permutations and Combinations

Successive calls to subroutine subprogram PERMU will generate all permutations of a set of integers of total length N consisting of $n$₁ repetitions of the integer 1, followed by $n$₂ repetitions of the integer $2,...$

etc, concluding with $n$_m repetitions of the integer m, where $\sum$_j=1^mn_j= N .

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

Successive calls to subroutine subprogram COMBI will generate all the $N\; J$ possible combinations without repetition of $J\; \le N$ integers from the set $1,2,...,N$ .

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 $\ge N$ . On entry, $IA(i),(i=1,2,...,N)$ , must contain the initial set of integers to be permuted (see Examples). A call with $IA(1)=0$ will place the set $1,2,...,N$ in IA. On exit, IA contains the "next" permutation. If all the permutations have been generated, the next call sets $IA(1)=0$ .

N

( INTEGER) Length of the set to be permuted.

    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 $\ge N$ . On exit, $IP(i),(i=1,2,...,N)$ , contains the NLX-th lexicographically ordered permutation of the integers $1,2,...,N$

(see Examples).

    CALL COMBI(IC,N,J)

IC

( INTEGER) One-dimensional array of length $\ge N+1$ . The first call must be made with $IC(1)=0$ . This generates the first combination $IC(i)=i,(i\; =\; 1,2,...,J)$ . 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 $IC(1)=0$ .

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:

   $y$₁,y₂,y₃,y,y,r₁,r₂,r,r,b,b,b.

   This set consists of m=8 sequences of length $n$₁=n₂=n₃=n₅=n₆=1 , $n$₄=n₇=2 , $n$₈= 3 . Thus, in order to get the possible permutations, set

   $IA\; =\; 1\; 2\; 3\; 4\; 4\; 5\; 6\; 7\; 7\; 8\; 8\; 8$

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

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

   permutions of the set $1,2,3,4$ :
   

   CALL PERMUT( 2,4,IP)	$IP\; =\; 1,2,4,3$
   CALL PERMUT( 3,4,IP)	$IP\; =\; 1,3,2,4$
   CALL PERMUT(24,4,IP)	$IP\; =\; 4,3,2,1$

4. To generate and print all 20 combinations of 3 integers from the set $1,2,3,4,5,6$ 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: $1\; \le NLX\; \le N!,\hspace{0.17em}N\; \le 12$ .
COMBI: $J\; \le N$ .

Error handling:

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

Notes:

1. If $N\; \le 0$ or $J\; \le 0$ , 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 $n$₁,n₂,...,n_m

   indistinguishable elements is given by

   $\{N!n$₁! n₂! ...n_m!}

   where $n$₁+n₂+...+n_m= N . This number can become large even for seemingly simple cases, e.g. in Example 1 above,

   $\{12!1!\hspace{0.17em}1!\hspace{0.17em}1!\hspace{0.17em}2!\hspace{0.17em}1!\hspace{0.17em}1!\hspace{0.17em}2!\hspace{0.17em}3!\}=\; 19958400.$

V300