Find The Minimum Difference

October 15, 2013

This is rather straight forward, though I admit it took a few tries to get all the less thans and minus signs in the right place:

(define (f xs ys)
  (let ((d (- (car xs) (car ys))))
    (let loop ((xs xs) (ys ys) (diff (abs d)))
      (cond ((or (null? xs) (null? ys)) diff)
            ((< (car xs) (car ys))
              (let ((d (- (car ys) (car xs))))
                (loop (cdr xs) ys (min d diff))))
            (else (let ((d (- (car xs) (car ys))))
                    (loop xs (cdr ys) (min d diff))))))))

For example:

> (f '(19 22 24) '(37 38 49 88))
13

The difference of 13 appears between 24 of the first array and 37 of the second array.

Assuming that the longer of the two arrays has length n, the algorithm given above has time complexity O(n). If the arrays weren’t sorted, you could sort them and then scan, giving a O(n log n) algorithm, or you could compare the items one-by-one for an O(n2) algorithm.

You can run the program at http://programmingpraxis.codepad.org/4bWj9XMf.

About these ads

Pages: 1 2

14 Responses to “Find The Minimum Difference”

  1. mattharrison86 said

    def find_smallest array1, array2
    	min = Float::INFINITY
    	array1.each_with_index { |elem1,i|
    		array2.each_with_index{ |elem2, j|
    			diff = (elem1 - elem2).abs
    			min = diff unless diff > min
    		}
    	}
    	min
    end
    
    puts find_smallest array1, array2 # 57
    
  2. Paul said

    In Python:

    def min_abs(arrx, arry):
        itx, ity = iter(arrx), iter(arry)
        x, y = next(itx, None), next(ity, None)
        diff = float("inf")
        while not None in (x, y):
            diff = min(diff, abs(x - y))    
            if x < y:
                x = next(itx, None)
            else:
                y = next(ity, None)
        return diff
    
  3. Graham said

    While this won’t change the average complexity, can’t we shortcircuit if we find an absolute difference of zero?

  4. Paul said

    We can shortcuit if we find a difference of one. Zero is not possible, as the arrays do not have common numbers.

  5. Graham said

    Thanks @Paul, I didn’t read carefully enough!

  6. Graham said

    I hate to be a pain, but it’s not clear to me that the arrays have to be nonempty.
    Here’s a Haskell version that handles empty lists as well:

    import Data.Maybe (fromJust)
    
    mad :: [Integer] -> [Integer] -> Maybe Integer
    mad [] _ = Nothing
    mad _ [] = Nothing
    mad xs ys = Just $ m xs ys z
        where
            z = abs . head $ zipWith (-) xs ys
            m [] _ d = d
            m _ [] d = d
            m (a:as) (b:bs) d | d' == 1   = 1
                              | a < b     = m as (b:bs) d'
                              | otherwise = m (a:as) bs d'
                              where
                                  d' = min d (abs $ a - b)
    
    
    main :: IO ()
    main = mapM_ (print . uncurry mad) [([], [1..]),
                                        ([1..], []),
                                        ([19, 22, 24], [37, 28, 49, 88])]
    

    This could have been cleaner if infinity were included in the integers in Haskell;
    it’s true that 1/0 returns Infinity, but this isn’t an Integer.

  7. Graham said

    Sorry for spamming, but here’s a slightly cleaner version of my mad function:

    mad :: [Integer] -> [Integer] -> Maybe Integer
    mad [] _ = Nothing
    mad _ [] = Nothing
    mad (x:xs) (y:ys) = Just $ m xs ys (abs $ x - y)
        where
            m [] _ d = d
            m _ [] d = d
            m (a:as) (b:bs) d | d' == 1   = 1
                              | a < b     = m as (b:bs) d'
                              | otherwise = m (a:as) bs d'
                              where
                                  d' = min d (abs $ a - b)
    
  8. Mike said

    Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

    def pairs(xs, ys):
    itx, ity = iter(xs), iter(ys)
    x, y = next(itx), next(ity)
    while True:
    yield x, y
    x, y = (next(itx),y) if x < y else (x, next(ity))

    def mindiff(xs, ys):
    return min(abs(x – y) for x,y in pairs(xs, ys))

  9. Mike said

    Sorry, forgot the formating.

    Python version. Like Paul’s, but i put the iterators in a separate generator that returns potential minimum pairs from the lists. Then maxdiff() is straight forward.

     
    
    def pairs(xs, ys):
        itx, ity = iter(xs), iter(ys)
        x, y = next(itx), next(ity)
        while True:
            yield x, y
            x, y = (next(itx),y) if x < y else (x, next(ity))
     
    def mindiff(xs, ys):
        return min(abs(x – y) for x,y in pairs(xs, ys))
    
    
  10. Eric said

    Here is my solution in groovy. I have a feeling there is a more efficient way to do this especially with the the def min at the start.

    static int minDiff(arr1, arr2){
    def min = Math.abs(arr1[0]-arr2[0])
    for(i in arr1){
    for(j in arr2){
    def diff = Math.abs(i-j)
    if(min>diff){
    min=diff
    }
    }
    }
    return min
    }

  11. Most of this stuff is well over my head, but I happen to be just starting to learn APL and so could’t resist. Using the example input from the first solution:

    f←{⌊/⌊/|⍺∘.-⍵}
    x←19 22 24
    y←37 38 49 88
    x f y
    13

    I don’t kow if there’s a clever mathy way to make it more efficient, but at least it has the virtue of simplicity. I guess this will run in O(n^2)… :-)

    As for empty vectors, I am not sure what the subtraction operator should yield without any arguments, but I get infinity when I feed it to my function:

    ⍬ f ⍬

  12. The Man From SQL said

    Here’s my version in C#. As a small optimization for large arrays, I’ve added a short-circuit that exits if the difference between x and y-currrent is positive and greater than the abs difference between x and y-previous (since the arrays are guaranteed to be sorted, this means we won’t find a smaller difference for x).

            public static int Find(int[] FirstArray, int[] SecondArray)
            {
                int minimum = Int32.MaxValue;
                int lastDiff;
    
                for (int i = 0; i < FirstArray.Length; i++)
                {
                    lastDiff = Int32.MaxValue;
    
                    for (int j = 0; j < SecondArray.Length; j++)
                    {   
                        int unAbsResult = SecondArray[j] - FirstArray[i];
                        int result = Math.Abs(unAbsResult);
                        if (result < minimum)
                        {
                            minimum = result;
                        }
                        if (result > lastDiff && unAbsResult > 0)
                        {
                            break;
                        }
                        
                        lastDiff = result;
                    }
                }
                return minimum;
            }
    
  13. Dakshin said

    Here is my version in C++:

    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define N 10

    struct small {
    int diff;
    int x;
    int i;
    int y;
    int j;
    } ;

    int get_num();
    int ascending(int *, int);

    int main(){

    int j,i=0;
    int n=N;
    int x[N];
    int y[N];
    int status;
    struct small sm;
    sm.x=sm.y=sm.i=sm.j=0;
    sm.diff=1000;

    while(i<n){
    x[i++] = get_num();
    }
    cout<<"X:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<x[i];
    cout<<' '<<endl;

    i=0;
    while(i<n){
    int num = get_num();
    status = false;

    for(j=0;j<n&&num==x[j];j++)
    status =true;

    if(status == false)
    y[i++]
    =num;

    }

    cout<<"Y:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<y[i];
    cout<<endl;

    cout<<"After ascending:"<<endl;
    ascending(x,n);
    cout<<"X:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<x[i];
    cout<<endl;

    ascending(y,n);
    cout<<"Y:"<<endl;
    for(i=0;i<n;i++)
    cout<<' '<<y[i];
    cout<<endl;

    for(i=0;i<n;i++)
    for(j=0;j<n;j++) {

    if(abs(x[i]-y[j]) <sm.diff)
    {
    sm.diff=abs(x[i]-y[j]);
    sm.i=i;
    sm.j=j;
    sm.x=x[i];
    sm.y=y[j];
    }

    }

    cout<<"diff:"<<sm.diff<<endl;
    cout<<"nums:"<<sm.x<<' '<<sm.y<<endl;

    return 0;
    }

    int get_num(){

    num:

    int n = rand()%100;

    if(n!=0)
    return n;
    else
    goto num;
    }

    int ascending(int *num, int n){

    int temp=0;
    int j,i=0;

    for(i=0;i<n;i++)
    for(j=0;jnum[j+1]){
    temp=num[j];
    num[j]=num[j+1];
    num[j+1]=temp;
    }

    }

    return true;
    }

  14. jozefg said

    A shorter haskell solution

    import Control.Monad
    minDiff (x:xs) (y:ys) | x – y < 0 = choose (y-x) $ minDiff xs (y:ys)
    | otherwise = choose (x-y) $ minDiff (x:xs) ys
    where choose x m = fmap (min x) m `mplus` Just x
    minDiff _ _ = Nothing

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: