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.
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 # 57In 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 diffWhile this won’t change the average complexity, can’t we shortcircuit if we find an absolute difference of zero?
We can shortcuit if we find a difference of one. Zero is not possible, as the arrays do not have common numbers.
Thanks @Paul, I didn’t read carefully enough!
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/0returnsInfinity, but this isn’t anInteger.Sorry for spamming, but here’s a slightly cleaner version of my
madfunction: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)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))
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))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
}
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 ⍬
∞
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; }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;
}
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