Gideon Ehrlich
Skip Abstract Section
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.
- 1 JOHNSON, S.M. Generat,on of permutations by adjacent transpositions. Math. Comput. 17 (1963), 282-285.Google Scholar
- 2 TROTTER, H.F. Algorithm 115, Perm Comm. A CM 5, 8 (Aug. 1962), 434-435. Google Scholar
- 3 EVEN, S. Algorithmic Combinatomcs Macmillan, New York, 1973, p. 2.Google Scholar
- 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).Google Scholar
- 5 ~,~D-S~ITH, R.J. Generation of permutation sequences: Part 2. Compuler J. 14 (May 1971), 136-139.Google Scholar
- 6 BOOTHROID, j. Algorithm 30. Computer J. 10 (1967), 310Google Scholar
- 7 GILBERT, E N Gray codes and paths on the n-cube. Bell Syst. Tech J 37 (May 1958), 815-826.Google Scholar
- 8 CHASE, P J. Algorithm 382, Combmatmns of M out of N objects. Comm. ACM lS, 6 (June 1970), 368 See also Remark on Algorithm 382, p. 376. Google Scholar
- 9 EHRLICH, G. PATEXACT: Generator of set-partitions to exactly R subsets (to appear).Google Scholar
Index Terms
- Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
Recommendations
A loopless algorithm for generating the permutations of a multiset
Random generation of combinatorial objects and bijective combinatoricsMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial ...
Combinatorial generation by fusing loopless algorithms
CATS '06: Proceedings of the Twelfth Computing: The Australasian Theory Symposium - Volume 51Some combinatorial generation problems can be broken into subproblems for which loopless algorithms already exist. We discuss means by which loopless algorithms can be fused to produce a new loopless algorithm that solves the original problem. We ...
Comments