/sci/ - Science & Math

[Anonymous No.3859530]

How would you go about finding the middle value of a list of numbers only by calculating max and min's of pairs
i.e: (max a(max b(max c (max d e))) would give you the maximum number out of the list

[Anonymous No.3859553]

1,2,4,5,7

min max min max min

yields 4

what do i win?

[Anonymous No.3859561]

If you have a list of 2n+1 numbers. You can first find the maximum of every subset with n+1 elements and then find the minimum of those maxima.

[TN5 !/sci/TN5.. No.3859593]

sys.4chan is down, so I'll have fun answering this properly.

I'll start by cheating using min and max on sequences if necessary, but that's just a shortcut in notations, and I'll fix it in the end.

Let's see what we can do with a list of 3 elements, a,b,c. A way to compute the median is to do:
<span class="math">\min( \max(\min(a,b),c) , \max(\min(b,c),a) , \max(\min(c,a),b) )[/spoiler]

Proof:
Assume (by symmetry) that <span class="math">a\leq b\leq c[/spoiler].
<span class="math">\max(min(a,b),c)=c[/spoiler]
<span class="math">\max(min(b,c),a)=b[/spoiler]
<span class="math">\max(min(c,a),b)=b[/spoiler]
<span class="math">\min(\max(\min(a,b),c),\max(\min(b,c),a),\max(\min(c,a),b))=\min(c&#
44;b,b)=b[/spoiler]

In a similar fashion, to know the 2nd highest among 4 elements, you do the min of the maxes of all triplets of elements. To know the 3rd highest among 5 elements, you do the min of the maxes of all triplets of elements.

In general, to know the <span class="math">k[/spoiler]-th highest among <span class="math">n[/spoiler] elements, you do the min of the maxes of all <span class="math">(n-k+1)[/spoiler]-tuples of elements, or the max of the mins of all <span class="math">k[/spoiler]-tuples, depending on whether <span class="math">k[/spoiler] or <span class="math">n-k+1[/spoiler] is lower.

This takes <span class="math">{n \choose k}[/spoiler] <span class="math">k[/spoiler]-ary mins, and 1 <span class="math">{n\choose k}[/spoiler]-ary max.

Each <span class="math">u[/spoiler]-ary min or max requires <span class="math">\lceil \log_2(u)\rceil[/spoiler] binary mins or maxes.

Thus it takes <span class="math">\lceil \log_2({n \choose k})\rceil+{n \choose k}\lceil \log_2(\mathrm{min}(k,n-k+1)\rceil<span class="math"> binary mins/maxes to compute the k-th largest (or lowest) element of a list of n elements using this method.

I would tend to think that it's optimal, or at least asymptotically optimal, but I don't have a proof or any idea about how to prove that.[/spoiler][/spoiler]

[TN5 No.3859639]

>>3859593
Will post well-formatted version in 10m. On cellphone atm.
Also, I'm pretty sure my solution is not optimal, now.

[TN5 !/sci/TN5.. No.3859663]

(reposted for bad formatting)
sys.4chan is down, so I'll have fun answering this properly.

I'll start by cheating using min and max on sequences if necessary, but that's just a shortcut in notations, and I'll fix it in the end.

Let's see what we can do with a list of 3 elements, a,b,c. A way to compute the median is to do:
<span class="math">\min( \max(\min(a,b),c) , \max(\min(b,c),a) , \max(\min(c,a),b) )[/spoiler]

Proof:
Assume (by symmetry) that <span class="math">a\leq b\leq c[/spoiler].
<span class="math">\max(min(a,b),c)=c[/spoiler]
<span class="math">\max(min(b,c),a)=b[/spoiler]
<span class="math">\max(min(c,a),b)=b[/spoiler]
<span class="math">\min(\max(\min(a,b),c), \max(\min(b,c),a), \max(\min(c,a),b)) =\min(c,b,b)=b[/spoiler]

In a similar fashion, to know the 2nd highest among 4 elements, you do the min of the maxes of all triplets of elements. To know the 3rd highest among 5 elements, you do the min of the maxes of all triplets of elements.

In general, to know the <span class="math">k[/spoiler]-th highest among <span class="math">n[/spoiler] elements, you do the min of the maxes of all <span class="math">(n-k+1)[/spoiler]-tuples of elements, or the max of the mins of all <span class="math">k[/spoiler]-tuples, depending on whether <span class="math">k[/spoiler] or <span class="math">n-k+1[/spoiler] is lower.

This takes <span class="math">{n \choose k}[/spoiler] <span class="math">k[/spoiler]-ary mins, and 1 <span class="math">{n\choose k}[/spoiler]-ary max.

Each <span class="math">u[/spoiler]-ary min or max requires <span class="math">\lceil \log_2(u)\rceil[/spoiler] binary mins or maxes.

Thus it takes <span class="math">\lceil \log_2({n \choose k})\rceil+{n \choose k}\lceil \log_2(\mathrm{min}(k,n-k+1)\rceil[/spoiler] binary mins/maxes to compute the <span class="math">k[/spoiler]-th largest (or lowest) element of a list of n elements using this method.

Also, like I said in the previous post, I don't think the construction is optimal anymore.

[TN5 !/sci/TN5.. No.3859871]

>>3859663
Actually, I just realized that what I wrote for 3 numbers doesn't match my construction from the rest of the post and is far worse.
It should have been:
<span class="math">max(min(a,b),min(b,c),min(a,c))[/spoiler]

Much more elegant.

[Anonymous No.3859882]

>>3859871
I posted this 3hours ago, just came back on the off chance someone might have replied, so thank you for taking the time.
I kind of understand what you're getting at, only trouble I'm having is the fact I can only find the min/max of 2 numbers at a time (using ocaml).

[Anonymous No.3859883]

I guess I would attempt to find the minimum and maximum of every subset, then eliminate them before the next iteration.

[TN5 !/sci/TN5.. No.3859900]

>>3859871
And also, to answer OP directly for 5 elements with a huge formula:
<span class="math">max(min(a,b,c),min(a,b,d),min(a,b,e),min(a,c,d),min(
a,c,e),min(a,d,e),min(b,c,d),min(b,c,e),min(b,d&
#44;e),min(c,d,e))[/spoiler]


Also, I'm wrong when I say that you need <span class="math">\lfloor \log_2(n)\rfloor[/spoiler] binary operations to replace a n-ary one. You need more than that. I'm wondering if it's possible to do it in less than n-1 operations. Actually I don't think it is.

[TN5 !/sci/TN5.. No.3859903]

>>3859882
Oh, you're using OCaml? T'es en MP*?

[Anonymous No.3859910]

>>3859903
Yep, 'T'es en MP' ??

[TN5 !/sci/TN5.. No.3859912]

(repost of >>3859900 to fix jsMath)

>>3859871
And also, to answer OP directly for 5 elements with a huge formula:
<span class="math">max(min(a,b,c),min(a,b,d),min(a,b,e),min(a,c,d),min( a,c,e),min(a,d,e),min(b,c,d),min(b,c,e),min(b,d&
#44;e),min(c,d,e))[/spoiler]


Also, I'm wrong when I say that you need <span class="math">\rfloor log2(n)\lfloor[/spoiler] binary operations to replace a n-ary one. You need more than that. I'm wondering if it's possible to do it in less than n-1 operations. Actually I don't think it is.

[TN5 !/sci/TN5.. No.3859917]

>>3859903
Anciennement. J'ai intégré y'a 6 ans.

[TN5 !/sci/TN5.. No.3859924]

>>3859912
Also what the hell is wrong with jsMath? I checked that what I posted was correct this time, with no strange character. Ascii character 44 is the coma, why is it escaped here? I don't get it...

[Anonymous No.3859927]

God knows, yeah figured it out, just trying to convert it to work in ocaml now, also I don't speak french

[TN5 !/sci/TN5.. No.3859928]

>>3859924
(Must have something to do with jsMath splitting long lines BEFORE unescaping htmlentities: I'll try with spaces to see if he splits in a more clever way)
<span class="math">max(min(a,b,c),min(a,b,d),min(a,b,e), min(a,c,d),min( a,c,e), min(a,d,e),min(b,c,d),min(b,c,e), min(b,d,e),min(c,d,e))[/spoiler]

[TN5 !/sci/TN5.. No.3859947]

>>3859927
Oh sorry about that. I said I was in MP* in 2004-2005.

Anyway, do you need OCaml to compute the result, or to compute the expression of formula? What's the exact exercise?

You can easily define min and max on list with OCaml by:
let min_list list = List.fold (fun a b -> min a b) min_int list
let max_list list = List.fold (fun a b -> max a b) max_int list

(assuming you deal with integer)
max_int and min_int are respectively the biggest and the smallest representable integer (already defined in OCaml)
List.fold_left is documented on http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html and is quite useful.

[Anonymous No.3859960]

Ahhh okay cool,
Yeah I've herd about some of them functions, however I'm not aloud to use them. The exact question is:
Implement a function that takes 5 ints and returns the median (middle) value without using the if statement.
You may use the predefined OCaml min and max functions.
The name and type is median5 : int * int * int * int * int -> int.

So far ive got:
let median5 (a, b, c, d, e) = max (min a (min b c) max (min a (min b d) max (min a(min b e) max (min a (min c d) max (min a (min c e) max (min a (min d e) max (min b (min c d) max (min b (min c e) max (min b (min d e) max (min c (min d e)))))))))));;

[TN5 !/sci/TN5.. No.3860035]

>>3859960
Okay, I see.
Well List.fold_left isn't really mysterious, you can code it yourself as a subfunction and it doesn't really use "if". Or well, it does use a match if you code it recursively, or a while if you code it iteratively, and in both cases, there's an implicit test... So maybe it's better not to do that.

I'd do:
let ab=min a b in
let ac=min a c in
let ad=min a d in
let bc=min b c in
let bd=min b d in
let cd=min c d in
max (min ab c)
(max (min ab d)
(max (min ab e)
(max (min ac d)
(max (min ac e)
(max (min ad e)
(max (min bc d)
(max (min bc e)
(max (min cd e)
)
)
)
)
)
)
)
)

(see pic for formatting)

I'll write a fast test protocol to check that it's correct.

[TN5 !/sci/TN5.. No.3860041]

>>3860035
And here's the missing pic...

[Anonymous No.3860065]

>>3860041
Thank you I'l have a look tomorrow morning

[TN5 !/sci/TN5.. No.3860137]

>>3860065
Also, I checked the validity of the function and it's correct.

See picture for the code for the verification. It builds all possible cases for a,b,c,d,e and tests the "min/max" version of the median computation vs one that sorts the list and picks the 3rd element, and an exception is raised if there's a discrepancy. The testing code is probably not optimal but works and looks nice enough (looks nice enough to make me want to code more, actually, but that's my general feeling about OCaml).