Board Logo
« finding max over array with tie-breaker »

Welcome Guest. Please Login or Register.
Nov 20th, 2017, 10:18pm


Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

Please use the forums Search feature before asking.
Please post code using the code box described in Format Your Messages.
This will keep indentation, separate it better form the message and prevent gibberish.
If the code is too long for one post or additional files are needed, upload a ZIP archive to the Just BASIC Files Archive Site.

« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: finding max over array with tie-breaker  (Read 729 times)
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 3614
xx finding max over array with tie-breaker
« Thread started on: Apr 2nd, 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 "tie-breaking". 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:
3 1 -> 31
3 2 -> 32
 

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 
User IP 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
ImageImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 1431
xx Re: finding max over array with tie-breaker
« Reply #1 on: Apr 2nd, 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 

User IP 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 Dual-Core Processor 2.10 GHz - 4.00 GB RAM (3.75 usable) - 64-bit OS
Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls