Scholarlink

<p>A universal cycle for <i>k</i>-permutations is a periodic sequence in which every <i>k</i>-permutation of the <i>n</i>-set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\{1,2,\ldots ,n\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>n</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> occurs exactly once within each period for all <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(n&gt;k\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>&gt;</mo> <mi>k</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we present two efficient algorithms to construct universal cycles for <i>k</i>-permutations. These two algorithms are built upon a concatenation tree framework proposed by Sawada et al.&#xa0;(2024), and each algorithm can be used to construct a universal cycle for <i>k</i>-permutations in <i>O</i>(1)-amortized time per symbol using <i>O</i>(<i>nk</i>) space.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient universal cycle constructions for k-permutations via concatenation trees

  • 期刊论文

  • 发表日期：

    2026年7月1日

查看全文
  • Lingyu Diao,
  • Zuling Chang,
  • Shujie Wang

摘要

A universal cycle for k-permutations is a periodic sequence in which every k-permutation of the n-set \(\{1,2,\ldots ,n\}\) { 1 , 2 , … , n } occurs exactly once within each period for all \(n>k\ge 3\) n > k ≥ 3 . In this paper, we present two efficient algorithms to construct universal cycles for k-permutations. These two algorithms are built upon a concatenation tree framework proposed by Sawada et al. (2024), and each algorithm can be used to construct a universal cycle for k-permutations in O(1)-amortized time per symbol using O(nk) space.