BOUNDS FOR SORTING BY PREFIX REVERSAL

被引：197

作者：

GATES, WH ^{[1
]}

PAPADIMITRIOU, CH ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DEPT ELECT ENGN,BERKELEY,CA 94720

来源：

DISCRETE MATHEMATICS | 1979年 / 27卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(79)90068-2

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a permutation σ of the integers from 1 to n, let f{hook}(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let f{hook}(n) be the largest such f{hook}(σ) for all σ in (the symmetric group) Sn. We show that f{hook}(n)≤ (5n+5) 3, and that f{hook}(n)≥ 17n 16 for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey 3n 2-1≤g(n)≤2n+3. © 1979.

引用

页码：47 / 57

页数：11