[Date Index] [Thread Index] [Author Index]

Gaylord's Problem extended

• To: mathgroup at smc.vnet.net
• Subject: [mg4891] Gaylord's Problem extended
• From: Jack Goldberg <jackgold at math.lsa.umich.edu>
• Date: Fri, 4 Oct 1996 00:17:32 -0400
• Sender: owner-wri-mathgroup at wolfram.com

Hi Group;

The problem of sorting a list by successive selection
of the max of the first and last entries I now dub 
as Gaylord's problem - in honor of his bringing it 
to this groups attention.  Here is a generalization 
which I think is also of interest:

Suppose we have  m  lists labelled  L1, L2, ..., Lm.
We select the maximum element from the set of first 
elements and delete this element from the list it 
was in.  We repeat this  r  times.  At any stage, if 
there is a tie, we take the entry from the list with 
the lowest subscript.  This process is unique and 
yields a list of "winners". (When an element is 
selected from a list, the second element in that 
list is now its first element.  Also, when a list 
is empty, the maximum is selected from the 
remaining lists.) 

Gaylord's problem is a special case in which  L1  is 
the given list and  L2  is the given list in 
reverse order and  r = Length[L1].  

Note:  The lists need not be of equal length but if 
it is convenient we can make them so by adding 
sufficiently many -Infinity 's  to the shorter 
lists.  The lists may even be defined recursively 
so that they need not be finite, but I suppose 
we should insist that  r  is finite.  

 So, experts, how should this be handled 
functionally?  I am sure that the solutions 
will be very instructive to those of us who 
study Mma through this site.

Jack Goldberg
Math
University of Michigan


==== [MESSAGE SEPARATOR] ====