Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] acqp_v1_0.gz(2 Kbytes)
Manuscript Title: An algorithm generating permutations with identical objects.
Authors: P. Basso, C. Bourrely
Program title: PERMID
Catalogue identifier: ACQP_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 1(1970)415
Programming language: Fortran.
Computer: UNIVAC 1108.
Operating system: EXEC II.
RAM: 1K words
Word size: 36
Keywords: General purpose, Combinatorial, Analysis, Permultations, Algebras.
Classification: 4.2.

Nature of problem:
For a given set of N objects where lambda1, lambda2, ..., lambdap are identical, we give an algorithm which generates all the distinct permutations of the n objects, without the necessity to store the permuted elements in order to compute the next ones. As an application of the algorithm we have written a Fortran subroutine generating these permutations.

Solution method:
In the case of distinct objects there exists the methods of group theory based upon cyclic permutations. When objects may be indentical the previous methods no longer apply, and in this case we have defined an algorithm where the permutations are reduced to commutations of elements according to a set of three operatorial rules. The method is similar in some respects to the treatment of non commutative algebras.

The program is applicable to permute integer numbers, but this restriction is easily removed by making a one to one correspondance between the integers and a finite set of objects.

Running time:
The running time depends on the number of ojects and their repartition in identical groups. As an example: for 2520 permutations 0.326 second, for 332040 permutations 42.65 seconds.