bug-gnubg
[Top][All Lists]

## Re: [Bug-gnubg] OT: An algorithm problem

 From: Joseph Heled Subject: Re: [Bug-gnubg] OT: An algorithm problem Date: Thu, 15 Feb 2007 17:29:27 +1300

```Since there was some interest here, this is the shortest (possibly

==================================================================
def m(s0, s1, n) :
# s0 and s1 are ordered
# find the n'th element in their union using O(lg(n)) comparisons

# Invariant: n'th element is in union of s0[:low[0] and s1[:low[1]]
s = (s0,s1)
low = [min(n,len(x)) for x in s]

# do while union contains more than n elements
while sum(low) > n :
nDiff = (sum(low) - n)/2

e = [s[i][low[i] - (1+nDiff)] for i in (0,1)]

# when nDiff is zero we need to decrement something :)
if nDiff == 0 : nDiff = 1

# if e[0] < e[1] there are more than n elements above e[1]. nither e[1]
# nor any element below are possible. same for reverse case
low[ e[0] < e[1] ] -= nDiff

v = [s[i][low[i]-1] for i in (0,1)]
if low[0] == 0 : return v[1]
if low[1] == 0 : return v[0]
return max(v)
==================================================================

You can test it with

n,k = 5,15 ; l = range(n+k) ; random.shuffle(l) ; l0,l1 = l[:n],l[n:]
; l0.sort() ; l1.sort() ;  assert m(l0,l1,n) == n-1

(and change n and k, of course)

-Joseph

On 2/15/07, Jim Segrave <address@hidden> wrote:
```
```On Wed 14 Feb 2007 (16:53 +0100), Øystein Johansen wrote:
> >Here's my idea :
> >Let's name S and T the two vectors.
> >F = {Fx = [S[i],T[j]] such that i+j+2=k}
> >(the +2 coming from python indexing starting at 0)
>
> Yes, this was also one of my first ideas. (Keeping two index i, j  in each
> array and having the sum of i and j fixed). I even suggested this solution to
> the lecturer, who didn't have a clue at that moment, and he claimed that this
> would work. He says he has implemented a MATLAB code that does this.
>
> [snip]
>
> Your code seems to work, however Joseph, found an even simpler way
> by using the i+j>k constrain as the end of iteration indicator. Really clever
> and simple to implement.
>
> I will take a look at Jims implementation as well. It really looks rigid
> but I'm not sure which method it uses. At first sight it looks like his idea
is
> the same as Josephs, just more code.

I think it's different - it tries to remove elements from S or T which
are known to be smaller than the element sought. One advantage, such
as it is, is that it copes with degenerate inputs where n is any
value, including 0. The constraint terminating iteration is that
enough items have been removed. I think that Massimiliano's requires
that n >= k (although I've not checked that and I could well be wrong).

If you take out the comments, asserts and debugging prints, it's
probably not much longer than the others, but perhaps not as elegant.
The debugging and asserts are there because the first couple of
versions which were almost the same idea worked 95% of the time, then
suddenly failed, so I got paranoid whether or not it was 100% correct/

I'm sorry to hear that the course is so unsatisfactory, because the
subject is an interesting one. I can't give any comparisions, because
when I was in university, the attitude there (Caltech) at the time
was that there was no reason to teach anything about computing,
computers were simply tools and you'd hardly offer a university course
on screwdrivers and hammers.

I'm sure that's changed by now.

--

_______________________________________________
Bug-gnubg mailing list
```