Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations

ABSTRACT

The purpose of this work is to find a method for building loopless algorithms for listing combinatorial items, like partitions, permutations, combinations. Gray code, etc. Algorithms for the above sequence are detailed in full.

REFERENCES

• 1: JOHNSON, S.M. Generat,on of permutations by adjacent transpositions. Math. Comput. 17 (1963), 282-285.
• 2: H. F. Trotter, Algorithm 115: Perm, Communications of the ACM, v.5 n.8, p.434-435, Aug. 1962 [doi>10.1145/368637.368660]
• 3: EVEN, S. Algorithmic Combinatomcs Macmillan, New York, 1973, p. 2.
• 4: EHRLm~, G. Four combinatoriM algorithms: PERMU. Permutations (to appear in Comm. A CM). COMBI: Combinations (to appear in Comm ACM). COMPOMIN: Compositions with minima (to appear in Comm. ACM). COMPOMAX: Compositions with maxima (to appear in Comm. A CM). See als~ PARTI' Part,t,ons of a set (m manuscript). GRAY2: Reflected binary Gray code (in manuscript).
• 5: ~,~D-S~ITH, R.J. Generation of permutation sequences: Part 2. Compuler J. 14 (May 1971), 136-139.
• 6: BOOTHROID, j. Algorithm 30. Computer J. 10 (1967), 310
• 7: GILBERT, E N Gray codes and paths on the n-cube. Bell Syst. Tech J 37 (May 1958), 815-826.
• 8: Phillip J. Chase, Algorithm 382: combinations of M out of N objects [G6], Communications of the ACM, v.13 n.6, p.368, June 1970 [doi>10.1145/362384.362502]
• 9: EHRLICH, G. PATEXACT: Generator of set-partitions to exactly R subsets (to appear).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Measurement, Performance, Theory, Verification