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] ====