Sorting networks are close to what I want, but not quite. A sorting network can be used to generate a min/max expression for the nth element. If we are sorting n elements a_1 through a_n, initialize strings e_1 through e_n to "a_1" through "a_n" respectively. Then when the network sorts a_i and a_j (i < j), set (e_1, e_j) <- ("min(" || e_i || "," || e_j || ")" , "max(" || e_i || "," || e_j || ")") where || is concatenation. When the network finishes, e_k will hold the min/max expression for the kth sorted element in terms of the original elements. If we are merely interested in counts, initialize list v_1 through v_n each to 1. When the network sorts a_i and a_j, replace each of v_i and v_j with v_i + v_j. When the network is finished, v_k gives the number of variables in the min/max expression e_k for the kth sorted element, and v_k - 1 gives the number of min/max operations in e_k. There is a 4-element (n = 4) sorting network illustrated at the beginning of the suggested Wiki article. If we compute the e_i and v_i for this network, we get e_1 = "min(min(a_1,a_3),min(a_2,a_4))" e_2 = "min(max(min(a_1,a_3),min(a_2,a_4)),min(max(a_1,a_3),max(a_2,a_4)))" e_3 = "max(max(min(a_1,a_3),min(a_2,a_4)),min(max(a_1,a_3),max(a_2,a_4)))" e_4 = "max(max(a_1,a_3),max(a_2,a_4))" with variable counts v_1 = 4 v_2 = 8 v_3 = 8 v_4 = 4 My apparently crude upper bound was v_k = n C(n-1, k-1), where the kth sorted element is obtained by taking the min over the maxes of every k-element subset. This gives v_1 = 4 v_2 = 12 v_3 = 12 v_4 = 4 So this particular sorting network beats my expression for the 2nd and 3rd sorted element out of 4. On the other hand, a 3-element sorting network (n = 3) must involve 3 sorts. Sorting elements ((a_1, a_2), (a_1, a_3), (a_2, a_3)) gives expressions e_1 = "min(min(a_1,a_2),a_3)" e_2 = "min(max(a_1,a_2),max(min(a_1,a_2),a_3))" e_3 = "max(max(a_1,a_2),max(min(a_1,a_2),a_3))" with v_1 = 3 v_2 = 5 v_3 = 5 whereas my upper bound is v_1 = 3 v_2 = 6 v_3 = 3 So this network generates a better expression for the 2nd element, but a worse for the 3rd. We could use the network's results to generate a better expression for e_3, namely e_3 = "max(max(a_1,a_2), a_3)" by min/max swapping on e_1, however, no 3-element sorting network simultaneously generates optimal expressions for both e_1 and e_3. So minimal sorting networks sometimes do better than my naive approach, but I don't think they necessarily generate optimal expressions, since they are interested in sorting all the elements, not simply finding the kth element. ----- Original Message ----- From: "Joshua Zucker" <joshua.zucker@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Friday, October 02, 2009 12:37 AM Subject: Re: [math-fun] minmax question
On Thu, Oct 1, 2009 at 8:25 PM, Tom Rokicki <rokicki@gmail.com> wrote:
Yeah, sorting "algorithms" generally require indexing.
This web page relates to what you want, I believe.
And then maybe these sequences are of some use: http://tinyurl.com/OEISsort (link to OEIS)
--Joshua
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-------------------------------------------------------------------------------- No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.409 / Virus Database: 270.14.1/2407 - Release Date: 10/01/09 06:34:00