| From: [email protected] (John Kececioglu)
Newsgroups: sci.math.research
Subject: Generating a permutation by reversals (SUMMARY)
Message-ID: <[email protected]>
Date: 28 Jan 92 22:53:47 GMT
Sender: Daniel Grayson <[email protected]>
Followup-To: comp.theory
Organization: U.C. Davis - Computer Science Division
Lines: 71
Originator: [email protected]
In early January I asked about the complexity of the following problem.
Instance: A permutation P of the integers 1 to N, and an integer K.
Question: Can P be expressed as a composition P = Q_1 Q_2 ... Q_m
of K or fewer permutations, where each Q_i simply reverses
the order of a group of consecutive elements, i.e., is of
the form
( a a+1 a+2 ... b )
Q_i = ( )
( b b-1 b-2 ... a )
Apparently, not much is known concerning its computational complexity.
Most responses observed that the maximum number of reversals necessary
to sort a permutation on N elements is between N/2 and N-1.
A few references. The problem is a special case of the following:
given a set of generators for the symmetric group and a permutation,
compute the shortest sequence of generators whose product is the permutation.
The following papers prove this more general problem is NP-complete.
S. Even and O. Goldreich,
"The minimum-length generator sequence problem is NP-hard,"
Journal of Algorithms 2 (1981) 311-313.
Mark R. Jerrum,
"The complexity of finding minimum-length generator sequences,"
Theoretical Computer Science 36 (1985) 265-289.
Other work bounds the maximum number of operations needed to sort a
permutation, as a function of the number of elements, for operations
other than reversals.
William H. Gates and Christos H. Papadimitriou,
"Bounds for sorting by prefix reversal,"
Discrete Mathematics 27 (1979) 47-57.
Martin Aigner and Douglas B. West,
"Sorting by insertion of leading elements,"
Journal of Combinatorial Theory (Series A) 45 (1987) 306-309.
The first paper considers sorting where the operation is to reverse a prefix,
and gives upper and lower bounds of (5n + 5)/3 and 17n/16. The second
considers sorting by repeatedly moving the first element, and shows that
exactly n-k moves are required, where k is the length of the longest
increasing suffix of the permutation.
My thanks to the following:
[email protected] (Boris Aronov)
[email protected] (Eric Bach)
[email protected] (Robert I. Eachus)
[email protected] (Scott Huddleston)
[email protected] (Simon Juden)
[email protected] (Nick Maclaren)
[email protected] (Ke Qiu)
[email protected] (Christian RONSE)
[email protected] (Douglas West)
--
John Kececioglu Computer Science Division
Email: [email protected] EECS Department
Phone: (916)752-8819 University of California
Fax: (916)752-4767 Davis, California 95616
|