XPost: comp.theory, sci.math   
   From: helms@uni-kassel.de   
      
   Mykola Rabchevskiy wrote:   
   >   
   > Browser wrote:   
   >   
   > > I have a list of N (x,y) pairs.  I want to return a list of all the   
   > > pairs (a,b) for which there is no other pair (A,B) with ((A>a and B>b)   
   > > or (A=a and B>b) or (A>a and B=b)).   
   > >   
   >   
   Since the logic of your composition is rather specific I would start   
   with a general solution like that:   
      
   Let the result of a compare-function of x,y be a value,   
   which is   
      1 if xy   
      
   =================================   
    for 1 dimension:   
      
     create a list of frequencies-counter with 3 bins:   
      
         counter 1     counter 2    counter 3   
           <              =            >   
         [       ]     [        ]   [        ]   
      
      
    Let the bins a one-dimensional array bins[1..3]   
      
      
     then do a double loop over your vector of data - either   
     just   
      
      bins: array [1..3] ;   
      bins=0 ;   
      for i=1 to n   
       for j=1 to n   
         inc(bins [comp(a[i],a[j]) ] ;   
      
      
     It would be better to reduce the j-loop to   
        for j=i+1 to n   
      
    Now this way you have only the frequencies. If you need the lists   
    the most simple thing is then to have these 3 bins at each   
    element of the list, and after the comparing pass you can   
    check which a[i]'s have the desired combination of freqs>0.   
      
      bins: array[1..n] of array [1..3] ;   
      bins:=0;   
      for i=1 to n   
       for j=1 to n   
         inc(bins [i], [comp(a[i],a[j]) ]   
      
      
      
   =================================   
      
    for 2 dimension I would do it analoguously   
      
    having the the bins a two-dimensional array then   
      
      
         counter 1,1     counter 1.2    counter 1.3   
           < <            < =            < >   
         [       ]      [        ]      [        ]   
      
         counter 2,1     counter 2.2    counter 2.3   
           = <            = =            = >   
         [       ]      [        ]      [        ]   
      
         counter 3,1     counter 3.2    counter 3.3   
           > <            > =            > >   
         [       ]      [        ]      [        ]   
      
      bins : array[1..3,1..3]   
      
      for i=1 to n   
       for j=1 to n   
         inc(bins  [  comp(a[i],a[j])  , comp(b[i],b[j]) ]   
      
    Again, to get a list, each list-element could get such an   
    square-bins-array   
      
      bins : array[1..n] of array[1..3,1..3]   
      bins=0   
      for i=1 to n   
       for j=1 to n   
         inc(bins [i]  [  comp(a[i],a[j])  , comp(b[i],b[j]) ]   
      
      
   ===========================   
      
   You can extend this easily to more dimension, I think.   
      
      
   The compare function can be enhanced, so that it returns   
   only a value 1 or 2, according tho the needs (and combinations)   
   of compare-results, which are "interesting" (returns 1)   
   and "not interesting" (returns 2).   
      
   Then you need only a simple list of bins:   
      
      bins : array[1..n] of array[1..2]   
      bins=0   
      for i=1 to n   
       for j=1 to n   
         inc(bins [i]  [  Interesting(a[i],a[j]  , b[i],b[j] ) ]   
      
      
      
      
   Gottfried Helms   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)