Programs in Physics & Physical Chemistry
|[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.|
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.
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.
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.
|Disclaimer | ScienceDirect | CPC Journal | CPC | QUB|