On a greedy algorithm to construct universal cycles for permutations

DOI10.1142/S0129054119400033MaRDI QIDQ5384431zbMATH OpenWikidataFDO

Authors Alice L. L. Gao, Sergey Kitaev, Wolfgang Steiner, Philip B. Zhang

Publication date 24 June 2019

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.10820

zbMATH Keywords

combinatorial generationgreedy algorithmpermutationsuniversal cycles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40)

Abstract: A universal cycle for permutations of length $n$ is a cyclic word or permutation, any factor of which is order-isomorphic to exactly one permutation of length $n$, and containing all permutations of length $n$ as factors. It is well known that universal cycles for permutations of length $n$ exist. However, all known ways to construct such cycles are rather complicated. For example, in the original paper establishing the existence of the universal cycles, constructing such a cycle involves finding an Eulerian cycle in a certain graph and then dealing with partially ordered sets. In this paper, we offer a simple way to generate a universal cycle for permutations of length $n$, which is based on applying a greedy algorithm to a permutation of length $n-1$. We prove that this approach gives a unique universal cycle $P{i}_n$ for permutations, and we study properties of $P{i}_n$.

Recommendations

• Universal cycles for permutations
• Universal cycles for permutation classes
• A new universal cycle for permutations
• Classifying rotationally-closed languages having greedy universal cycles
• Equivalence class universal cycles for permutations

Cites work

• A problem in arrangements
• An explicit universal cycle for the (n-1)-permutations of an n-set
• Equivalence class universal cycles for permutations
• Faster generation of shorthand universal cycles for permutations
• Hamiltonicity of digraphs for universal cycles of permutations
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• On shortening u-cycles and u-words for permutations
• Shorthand universal cycles for permutations
• Universal cycles for combinatorial structures
• Universal cycles for permutation classes
• Universal cycles for permutations
• Universal cycles of k-subsets and k-permutations

Cited in

(7)

• Classifying rotationally-closed languages having greedy universal cycles
• Shortened universal cycles for permutations
• scientific article; zbMATH DE number 177149 (Why is no real title available?)
• Constructing the first (and coolest) fixed-content universal cycle
• An explicit universal cycle for the (n-1)-permutations of an n-set
• On a family of universal cycles for multi-dimensional permutations
• On shortening universal words for multi-dimensional permutations

This page was built for publication: On a greedy algorithm to construct universal cycles for permutations

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