A Gray code for set partitions

DOI10.1016/0020-0190(76)90014-4MaRDI QIDQ1239129zbMATH OpenOpenAlexFDO

Authors Richard Kaye

Publication date 1976

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(76)90014-4

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Communication theory (94A05)

Review text

A Gray code for the set of partitions of \(\{1,\ldots,n\}\) is an ordered list of the partitions with the property that any partition is obtained from its predecessor by moving one letter. The author gives two constructions for such a Gray code, one recursive, the other direct. An algorithm for the second construction is given; it has the property that the average work per partition is bounded independent of \(n\).

Recommendations

• Gray code sequences of partitions
• Gray codes, loopless algorithm and partitions
• Gray code enumeration of families of integer partitions
• Loop-free Gray code algorithms for the set of compositions
• scientific article; zbMATH DE number 731846

Cited in

(25)

• Gray codes for non-crossing partitions and dissections of a convex polygon
• Gray codes, loopless algorithm and partitions
• Gray codes for column-convex polyominoes and a new class of distributive lattices
• Rekursive Erzeugung aller Partitionen einer endlichen Menge
• Gray code enumeration of families of integer partitions
• Gray codes for reflection groups
• Loop-free Gray code algorithm for the \textbf{e}-restricted growth functions
• Gray cycles of maximum length related to \(k\)-character substitutions
• Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
• The greedy Gray code algorithm
• Gray code sequences of partitions
• m-compositions and m-partitions: exhaustive generation and Gray code
• scientific article; zbMATH DE number 5975298 (Why is no real title available?)
• Permutational labelling of constant weight Gray codes
• scientific article; zbMATH DE number 731846 (Why is no real title available?)
• Infinite-valued first-order Łukasiewicz logic: hypersequent calculi without structural rules and proof search for sentences in the prenex form
• Numbering of set partitions
• scientific article; zbMATH DE number 1396785 (Why is no real title available?)
• Gray codes and lexicographical combinatorial generation for nonnesting and sparse nonnesting set partitions
• Gray codes for noncrossing and nonnesting partitions of classical types
• ALGORITHMS FOR LABELING CONSTANT WEIGHT GRAY CODES
• Combinatorial generation via permutation languages. I: Fundamentals
• Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions
• Maximize the rightmost digit: Gray codes for restricted growth strings
• Combinatorial generation via permutation languages. IV: Elimination trees

This page was built for publication: A Gray code for set partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1239129)