Match Three or More Nearest Numbers from arrays - 【StackMirror】|algorithm|matching|minimum

I have four arrays of size 2^N where N = 25. The elements of arrays have been generated by my algorithm. These are sorted but contain numbers. Now I have to take each element of array1 and select elements of array2, array3, array4 such that sum of them should be minimum (when I say sum I can take a1[k] +-a2[j]+-a3[m]+-a4[t]. I think it is similar to K Dimension merge problem. Can some one point to the literature/implementation /heuristic for doing the same. Regards, Allahbaksh

2012-04-04 06:26
by Allahbaksh Asadullah

An example will be very helpful. 2. You can use the ± sign.

- Adam Matan 2012-04-04 06:29

What you are asking in words is trivial - take the minimal elements from array2, 3 and 4, regardless of the element of array1, then also the sum will be minimal. But I suspect you want to know something different - Doc Brown 2012-04-04 06:38

Step 1 For array1[k], find a number in array2 or array3 or array4 such that its modulus is closer to array1[k].

eg . 
array1 = {1, 3, 67}
array2 = {-31, 7, 47}
array3 = {-1, 2, 10}
array4 = {14, 15, 66}

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1

Step 2 Then of the remaining 2 arrays, find a pair of numbers which are closer to each other. (again consider modulus)

eg . 
array2 = {-31, 7, 47}
array4 = {14, 15, 66}

Closest elements are 7 and 14 with -7 + 14 = 7.

Eventually you get min(a1[k] +-a2[j]+-a3[m]+-a4[t]) from all 4 arrays.

2012-04-04 06:43
by Tejas Patil

So for 1 from array1 this gives: 1 - 1 - 7 + 14 = 7? But you can do better: 1 + 7 + 10 - 14 = 4 - Henrik 2012-04-04 07:15

This will blow up solution exponentially. I think the brute force way of doing this is to put it in for loop. So 4 for loop for four array which will take huge computation power as N increases. Are there any heuristic algorithm for KDM merge - Allahbaksh Asadullah 2012-04-04 18:27

@Henrick : good catch. i need to revisit the approach - Tejas Patil 2012-04-04 18:32

Actually nearest would be 3,7,10,14 -> distance is 1 - Ruslan Dzhabbarov 2012-08-21 21:43

I think this problem could be solved in O(n), merge all arrays in union set so second value will be array number. Iterate through it and on each iteration form answer from 4 values, on each step calculate maximum distance between selected numbers -> minimize this value.
Init result array with smallest numbers from each array.

public Integer[] findClosest(int[][] unionSet, Integer[] result) {

    for (int i = 0; i < unionSet.length; i++) {
        int value = unionSet[i][0];
        int position = unionSet[i][1];
        int currentDistance = getDistance(result);
        Integer[] temp = Arrays.copyOf(result, result.length);
        temp[position] = value;
        int newDistance = getDistance(temp);
        if (newDistance <= currentDistance) {
            result = temp;
        }
    }
    return result;
}

private int getDistance(Integer[] result) {
    int max = 0;
    int min = 0;
    for (int i = 1; i < result.length; i++) {
        if (result[i] != null) {
            if (result[i] > result[max]) {
                max = i;
            }
            if (result[min] != null && result[i] < result[min]) {
                min = i;
            }
        }
    }

    return Math.abs(result[max] - result[min]);
}

2012-08-21 18:28
by Ruslan Dzhabbarov