INHOMOGENEOUS SORTING

被引：17

作者：

ANISIMOV, AV ^{[1
]}

KNUTH, DE ^{[1
]}

机构：

[1] STANFORD UNIV,CTR COMP,STANFORD,CA 94305

来源：

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES | 1979年 / 8卷 / 04期

关键词：

Commutativity; partial order; sorting; topological sorting;

D O I：

10.1007/BF00993053

中图分类号：

G25 [图书馆学、图书馆事业]; G35 [情报学、情报工作];

学科分类号：

1205 ; 120501 ;

摘要：

The purpose of this paper is to consider a special kind of sorting problem in which a sequence a1 ... an is to be rearranged into an optimal order by interchanging pairs of adjacent elements, where certain pairs of elements are not allowed to commute with each other. Section 1 presents an informal example intended to clarify the nature of the problem, while Secs. 2 and 3 give some formal definitions and characterizations. Section 4 shows that the problem we are considering is equivalent to finding the lexicographically smallest topological sorting in a partial order. © 1979 Plenum Publishing Corporation.

引用

页码：255 / 260

页数：6