Loopless generation of multiset permutations using a constant number of variables by prefix shifts

ABSTRACT

This paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. This paper also answers the following algorithmic question: Can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? Previously, the best loopless algorithm used a linear amount of additional storage. The answers to these questions are both yes.

REFERENCES

• 1: G. Betta A. Pietrosanto A. Scaglione. A Gray-code-based fiber optic liquid level transducer. IEEE Transactions on Instrumentation and Measurement, 47(1):174--178, February 1998.
• 2: F. Ruskey A. Williams. Generating combinations by prefix shifts. In COCOON '05: Computing and Combinatorics, 11th Annual International Conference, volume 3595 of Lecture Notes in Computer Science, Kunming, China, 2005. Springer-Verlag.
• 3: F. Ruskey A. Williams. The coolest way to generate combinations. Discrete Mathematics, (in press), 2008.
• 4: F. Ruskey A. Williams. An explicit universal cycle for the (n - 1)-permutations of an n-set. ACM Transactions on Algorithms, (submitted), 2008.
• 5: Frank Ruskey , Aaron Williams, Generating balanced parentheses and binary trees by prefix shifts, Proceedings of the fourteenth symposium on Computing: the Australasian theory, January 01-01, 2008, Wollongong, NSW, Australia
• 6: Terry MinYih Wang , Carla D. Savage, A Gray Code for Necklaces of Fixed Density, SIAM Journal on Discrete Mathematics, v.9 n.4, p.654-673, Nov. 1996 [doi>10.1137/S089548019528143X]
• 7: Chun Wa Ko , Frank Ruskey, Generating permutations of a bag by interchanges, Information Processing Letters, v.41 n.5, p.263-269, April 3, 1992 [doi>10.1016/0020-0190(92)90170-Z]
• 8: Gara Pruesse , Frank Ruskey, Generating Linear Extensions Fast, SIAM Journal on Computing, v.23 n.2, p.373-386, April 1994 [doi>10.1137/S0097539791202647]
• 9: Ming Jiang , Frank Ruskey, Determining the Hamilton-connectedness of certain vertex-transitive graphs, Discrete Mathematics, v.133 n.1-3, p.159-169, Oct. 15, 1994 [doi>10.1016/0012-365X(94)90023-X]
• 10: Joe Sawada , Frank Ruskey, An efficient algorithm for generating necklaces with fixed density, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.752-758, January 17-19, 1999, Baltimore, Maryland, United States
• 11: Frank Ruskey , Joe Sawada, An Efficient Algorithm for Generating Necklaces with Fixed Density, SIAM Journal on Computing, v.29 n.2, p.671-684, Oct. 1999 [doi>10.1137/S0097539798344112]
• 12: Frank Ruskey , Joe Sawada, A fast algorithm to generate unlabeled necklaces, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.256-262, January 09-11, 2000, San Francisco, California, United States
• 13: V. Vajnovszki M. Weston. Gray codes for necklaces and lyndon words of arbitrary base. Pure Mathematics and Applications/Algebra and Theoretical Computer Science, 17(1--2):175--182, 2006.
• 14: Fan Chung , Persi Diaconis , Ron Graham, Universal cycles for combinatorial structures, Discrete Mathematics, v.110 n.1-3, p.43-59, Dec. 11, 1992 [doi>10.1016/0012-365X(92)90699-G]
• 15: J. F. Korsh P. S. LaFollette. Loopless generation of linear extensions of a poset. Order, 18(2):115--126, 2002.
• 16: J. F. Korsh P. S. LaFollette. Loopless array generation of multiset permutations. The Computer Journal, 47(5):612--621, 2004.
• 17: E. R. Canfield S. G. Williamson. A loop-free algorithm for generating the linear extensions of a poset. Order, 12(1):57--75, 1995.
• 18: P. Diaconis S. Holmes. Gray codes for randomization procedures. Statistical Computing, 4:207--302, 1994.
• 19: James Korsh , Seymour Lipschutz, Generating multiset permutations in constant time, Journal of Algorithms, v.25 n.2, p.321-335, Nov. 1997 [doi>10.1006/jagm.1997.0889]
• 20: R. Sawae T. Sakata M. Tei K. Takarabe Y. Manmoto. Gray code and the initialization problem of NMR quantum computers. International Journal of Quantum Chemistry, 95:558--560, 2003.
• 21: P. F. Corbett, Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks, IEEE Transactions on Parallel and Distributed Systems, v.3 n.5, p.622-626, September 1992 [doi>10.1109/71.159045]
• 22: N. G. de Bruijn. A combinatorial problem. Koninkl. Nederl. Acad. Wetensch. Proc. Ser A, 49:758--764, 1946.
• 23: Gideon Ehrlich, Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations, Journal of the ACM (JACM), v.20 n.3, p.500-513, July 1973 [doi>10.1145/321765.321781]
• 24: F. Gray. Pulse code communication. U.S. Patent 2,632,058, 1947.
• 25: J. R. Johnson. Universal cycles for permutations. Discrete Mathematics, (in press), 2008.
• 26: S. M. Johnson. Generation of permutations by adjacent transpositions. Mathematics of Computation, 17:282--285, 1963.
• 27: Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions, Addison-Wesley Professional, 2005
• 28: Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming), Addison-Wesley Professional, 2005
• 29: Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation (Art of Computer Programming), Addison-Wesley Professional, 2006
• 30: Frank Ruskey, Generating linear extensions of posets by transpositions, Journal of Combinatorial Theory Series B, v.54 n.1, p.77-101, Jan. 1992 [doi>10.1016/0095-8956(92)90067-8]
• 31: Carla Savage, A Survey of Combinatorial Gray Codes, SIAM Review, v.39 n.4, p.605-629, Dec. 1997 [doi>10.1137/S0036144595295272]
• 32: Joe Sawada, A fast algorithm to generate necklaces with fixed content, Theoretical Computer Science, v.301 n.1-3, p.477-489, 14 May 2003 [doi>10.1016/S0304-3975(03)00049-5]
• 33: Tadao Takaoka, An O(1) Time Algorithm for Generating Multiset Permutations, Proceedings of the 10th International Symposium on Algorithms and Computation, p.237-246, December 16-18, 1999
• 34: Takao Ueda, Gray codes for necklaces, Discrete Mathematics, v.219 n.1-3, p.235-248, May 2000 [doi>10.1016/S0012-365X(99)00348-9]
• 35: Vincent Vajnovszki, A loopless algorithm for generating the permutations of a multiset, Theoretical Computer Science, v.307 n.2, p.415-431, 7 October 2003 [doi>10.1016/S0304-3975(03)00228-7]
• 36: Vincent Vajnovszki, More restrictive Gray codes for necklaces and Lyndon words, Information Processing Letters, v.106 n.3, p.96-99, April, 2008 [doi>10.1016/j.ipl.2007.10.011]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations