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

[Joseph Heled]

Since there was some interest here, this is the shortest (possibly
readable) effort from me

==================================================================
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.
>
> --
> Jim Segrave           address@hidden
>
>
>
> _______________________________________________
> Bug-gnubg mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/bug-gnubg