[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1539.0. "Permutations by reversals problem." by CADSYS::COOPER (Topher Cooper) Thu Jan 09 1992 12:50

From: kece@iro.umontreal.ca (John Kececioglu)
Newsgroups: sci.math.research
Subject: Generating a permutation by reversals
Keywords: symmetric group, generator sequences, NP-completeness
Message-ID: <1992Jan8.213718.2166@IRO.UMontreal.CA>
Date: 8 Jan 92 21:37:18 GMT
Sender: Daniel Grayson <dan@math.uiuc.edu>
Organization: Universite de Montreal
Lines: 36


Does anyone know of any complexity results related to 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 )


Stated another way, what is the fewest number of operations to put a list of
numbers in ascending order, where an operation reverses a whole sublist at
once.

Please email me directly; I'll collect the responses and post a summary to
the net.

Thanks,
John


John Kececioglu                         Centre de recherches mathematiques
Email: kece@crm.umontreal.ca            Universite de Montreal
Phone: 514-343-7501                     C.P. 6128, succursale A
Fax:   514-343-2254                     Montreal, Quebec H3C 3J7
T.RTitleUserPersonal
Name		DateLines
1539.1sounds familiar, but not quite...CIVAGE::LYNNLynn Yarbrough @WNP DTN 427-5663Thu Jan 09 1992 15:232
See note 425 for the related problem in which only an initial vector may be 
reversed.
1539.2Citations on the problem.CADSYS::COOPERTopher CooperThu Jan 30 1992 13:2582
From: kece@eecs.ucdavis.edu (John Kececioglu)
Newsgroups: sci.math.research
Subject: Generating a permutation by reversals (SUMMARY)
Message-ID: <10936@ucdavis.ucdavis.edu>
Date: 28 Jan 92 22:53:47 GMT
Sender: Daniel Grayson <dan@math.uiuc.edu>
Followup-To: comp.theory
Organization: U.C. Davis - Computer Science Division
Lines: 71
Originator: kece@ivy.cs.ucdavis.edu



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:

	aronov@ziggy.poly.edu (Boris Aronov)
	bach@cs.wisc.edu (Eric Bach)
	eachus@d74sun.mitre.org (Robert I. Eachus)
	scott@ferrari.labs.tek.com (Scott Huddleston)
	S.Juden@gdr.bath.ac.uk (Simon Juden)
	nmm@cl.cam.ac.uk (Nick Maclaren)
	qiu@qucis.queensu.ca (Ke Qiu)
	ronse@geocub.greco-prog.fr (Christian RONSE)
	west@uiucmath.math.uiuc.edu (Douglas West)


-- 
John Kececioglu                         Computer Science Division
Email: kece@cs.ucdavis.edu              EECS Department
Phone: (916)752-8819                    University of California
Fax:   (916)752-4767                    Davis, California 95616