Generating Gray codes for weak orders in constant amortized time

Marsden Jacques, Dennis Wong, Kyounga Woo

研究成果: Article同行評審

摘要

A weak order is a way to rank n objects where ties are allowed. In this paper, we develop a generic framework to generate Gray codes for weak orders. We then describe a simple algorithm based on the framework that generates cyclic 2-Gray codes for weak orders in constant amortized time per string. This is the first known cyclic 2-Gray codes for weak orders. The framework can easily be modified to generate other Gray codes for weak orders. We provide an example of using the framework to generate the first shift Gray codes for weak orders in constant amortized time per string, where consecutive strings differ by a shift or a symbol change.

原文English
文章編號111992
期刊Discrete Mathematics
343
發行號10
DOIs
出版狀態Published - 10月 2020
對外發佈

指紋

深入研究「Generating Gray codes for weak orders in constant amortized time」主題。共同形成了獨特的指紋。

引用此