Author 
Topic: finding max over array with tiebreaker (Read 804 times) 

tsh73
JBSupporter
member is offline
Gender:
Posts: 3648


finding max over array with tiebreaker
« Thread started on: Apr 2^{nd}, 2015, 12:48pm » 

If we want to find a maximum over array ("best value" in some sence), it is pretty strightforward: Code:for i = 1 to n
if a(i) > max then max=a(i): maxPos=i
next Or in complete program Code:randomize .53
n=10
dim a(n)
'fill
for i = 1 to n
a(i)=int(rnd(1)*3)+1
next
'find best (: max)
max = 0
maxPos= 0
for i = 1 to n
if a(i) > max then max=a(i): maxPos=i
next
'print
for i = 1 to n
print i, a(i),
if i=maxPos then print "Best one" else print
next But wait. We see two max values, which one to choose? Code:1 1
2 1
3 1
4 1
5 1
6 1
7 2
8 3 Best one
9 3
10 1
Actually, if we have no other information, we could choose either (even at random). But sometimes we could say "if values match, we have next ordering to use"  to use for "tiebreaking". Like this. Code:randomize .53
n=10
dim a(2,n)
'fill
for i = 1 to n
a(1,i)=int(rnd(1)*3)+1
next
for i = 1 to n
a(2,i)=int(rnd(1)*3)+1
next
'find best (: max)
max = 0
maxPos= 0
for i = 1 to n
if a(1,i) > max then max=a(1,i): maxPos=i
next
'print
for i = 1 to n
print i, a(1,i);" ";a(2,i),
if i=maxPos then print "Best one" else print
next Code:1 1 3
2 1 2
3 1 1
4 1 2
5 1 2
6 1 3
7 2 1
8 3 1 Best one
9 3 2
10 1 1 Oops. Now, we are pretty sure we better take second one. Now, the question is  how to program that?
The answer is *folding* We should combine two numbers into one so first one matters most, and if they match, program compare second one. And indeed it's pretty straightforward: Code: the formula is Code:first_value*weight+second_value and weight should be bigger then max(second_value) so second value matters only if first value match. It could be generalised to more values. Code:randomize .53
n=10
dim a(2,n)
'fill
for i = 1 to n
a(1,i)=int(rnd(1)*3)+1
next
for i = 1 to n
a(2,i)=int(rnd(1)*3)+1
next
'find best (: max)
max = 0
maxPos= 0
for i = 1 to n
'fold a(1,i) and a(2,i) into one number so we can check it at once
'use "weight" so a(1,i) is more impotrant
'"weight" whould be greater then max (a(2,i)), so we take 10
fold = a(1,i)*10+a(2,i)
if fold > max then max=fold: maxPos=i
'it could be generalised to several orders, like
'fold = a(1,i)*10^3+a(2,i)*10^2+a(3,i)*10+a(4,i)
next
'print
for i = 1 to n
print i, a(1,i);" ";a(2,i),
if i=maxPos then print "Best one" else print
next Code:1 1 3
2 1 2
3 1 1
4 1 2
5 1 2
6 1 3
7 2 1
8 3 1
9 3 2 Best one
10 1 1


Logged

Q: "And if I took your codes and compile them, and sell them for a profit"? A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it  please do. (enjoying JB 1.01 on WinXP, netbook and desktop)



TyCamden
Global Moderator
member is offline
Gender:
Posts: 1431


Re: finding max over array with tiebreaker
« Reply #1 on: Apr 2^{nd}, 2015, 1:51pm » 

The folding idea is very nice, and works well.
Normally I would have accomplished the task as follows, but I do like seeing other ways to do it...
Code:randomize .53
n=10
dim a(2,n)
'fill
for i = 1 to n
a(1,i)=int(rnd(1)*3)+1
next i
for i = 1 to n
a(2,i)=int(rnd(1)*3)+1
next i
'find best (: max)
max = 0
maxPos= 0
for i = 1 to n
select case
case a(1,i) > max
max=a(1,i)
maxPos=i
case a(1,i) = max
if a(2,i) > a(2,maxPos) then
max=a(1,i)
maxPos=i
end if
case else
' ignore
end select
next i
'print
for i = 1 to n
print i, a(1,i);" ";a(2,i),
if i=maxPos then
print "Best one"
else
print
end if
next


Logged

TyCamden
Please give credit if you use code I post, no need to ask for permission.
Just BASIC 1.01, Windows 7 Home Premium version (2009), AMD Athelon II 320 DualCore Processor 2.10 GHz  4.00 GB RAM (3.75 usable)  64bit OS



