Containing All Permutations

Abstract Numerous versions of the question “what is the shortest object containing all permutations of a given length?” have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.

摘要 在过去的五十年中，“包含给定长度的所有排列的最短对象是什么？”这一问题有众多版本被提出：1972年由卡普（通过高德纳）提出；1992年由钟、迪亚科尼斯和格雷厄姆提出；1993年由阿什洛克和蒂洛森提出；1999年由阿拉蒂亚提出。这种形式的问题种类繁多，此前都是孤立地被考虑，这与答案的匮乏形成了鲜明对比。我们综述并综合这些问题及其部分答案，引入更多相关问题，然后为其中一个问题建立一个改进的上界。