主题
Search

排列游程

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook

在一个排列中，一组升序序列被称为一个游程（Graham et al. 1994）或有时称为上升（Comtet 1974, p. 241）。一个已排序的排列由单个游程组成，而一个逆序排列由 n 个游程组成，每个游程的长度为 1。排列 p 中的排列游程可以使用以下方法计算游程[p] 在 Wolfram Language 包中Combinatorica`。具有 k 个游程的 {1,2,...,n} 的划分的排列游程数有时表示为 a(n,k) (Comtet 1974, p. 241)。

例如，排列 {1,2} 包含单个游程 {1,2}，而 {2,1} 包含两个游程 {2} 和 {1}。下表列出了 {1,2,3} 的每个排列 p 的排列游程。

p排列游程
{1,2,3}{1,2,3}
{1,3,2}{1,3}, {2}
{2,1,3}{2}, {1,3}
{2,3,1}{2,3}, {1}
{3,1,2}{3}, {1,2}
{3,2,1}{3}, {2}, {1}

长度为 n 且正好有 k 个游程的排列数 a(n,k) 与 排列上升的数目直接相关，其中 k 个游程意味着 k-1 个上升 (Comtet 1974, p. 241; Skiena 1990, p. 31)，因此

a(n,k)=<n; k-1>,

其中 <n; k-1> 是一个 欧拉数。

令人惊讶的是，第一个游程的预期长度比第二个游程的预期长度短 (Gassner 1967; Skiena 1990, p. 30; Knuth 1998)。

参见

欧拉数, 排列, 排列上升, 游程

通过 Wolfram|Alpha 探索

参考文献

Comtet, L. "Permutations by Number of Rises; Eulerian Numbers." §6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 240-246, 1974.Gassner, B. J. "Sorting by Replacement Selection." Comm. ACM 10, 89-93, 1967.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Mannila, H. "Measures of Presortedness and Optimal Sorting Algorithms." IEE Trans. Comput. 34, 318-325, 1985.Skiena, S. "Runs and Eulerian Numbers." §1.3.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 30-31, 1990.

在 Wolfram|Alpha 上被引用

排列游程

请引用为

Weisstein, Eric W. "排列游程." 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/PermutationRun.html

学科分类