CODEWITHSUNDEEP
javascriptalgorithm
tnkh
tnkh

Reputation: 1839

Shortest distance between objects

let say I have an object such that :

let objs = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] }

Each obj has more than one distance points, but only one should be chosen to combine with other obj's distance point.

I can combine three objects based on the distance points above in 12 ways.

For example, it could become [0,3,5]; In this case , the total distance between three objects would be 5 - 0 which is 5;

Or it can become [10, 9, 5], and the distance is 10 - 5 = 5;

The combination can also be [0, 3, 12] and the distance is 12 - 0 = 12;

What I intend to achieve is to find the shortest combination, which in this case should be [10, 9, 12]; and the distance is 12-9 =3;

So I have thought of performing combinations one by one; I can do nested loop to do that but it would be very inefficient. What is the most efficient method I can use to achieve this?

Upvotes: 3

Views: 804

Answers (3)

Bergi
Bergi

Reputation: 664936

I don't think there's anything better than nested/recursive loops, in the worst case you will still need to examine all combinations. However, I think applying the branch-and-bound algorithm will give a good optimisation as it will prune branches with not-so-good distances early - also taking advantage of the fact that your points per objects are sorted, so you can prune multiple choices at once.

Actually, for each object we can prune to just 2 choices that are nearest-below and nearest-above the interval selected so far. I would therefore estimate a worst-case complexity of O(k * (2+log k)n) (given n objects with on average k already-sorted points), not the O(kn) of the naive enumeration.

Admittedly, this is worse than the O(kn log(kn) + kn²) of Nina's second approach or the O(kn log(kn)) of Maras' algorithm - which can be further improved to O(kn log n) by using a n-way merge on already-sorted lists.

Upvotes: 3

Nina Scholz
Nina Scholz

Reputation: 386680

You could get the cartesian product and then reduce the array by taking the one with the smaller delta of max and min value.

let objects = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] },
    data = Object.values(objects),
    cartesian = data.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), [])),
    result = cartesian.reduce((a, b) => Math.max(...a) - Math.min(...a) < Math.max(...b) - Math.min(...b) ? a : b)

console.log(result);
console.log(cartesian.map(a => a.join(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

A faster approach uses a sorted array and takes only the last three items of every array in sorted order.

This is a linear search without using a cartesian product.

index  values                delta
-----  --------------------  -----
   0    0          10 
   1       3     9
   2          5       12 14
       --------                 5
       --    -----              9
             --------           5
                --------        3 <-- min
                ------   --     5


let objects = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] },
    data = Object
        .values(objects)
        .map((a, i) => a.map(v => [v, i]))
        .reduce((a, b) => a.concat(b))
        .sort((a, b) => a[0] - b[0] || a[1] - b[1]),
    parts = [undefined, undefined, undefined],
    result,
    i;

for (i = 0; i < data.length; i++) {
    parts[data[i][1]] = data[i][0];
    if (parts.some(v => v === undefined)) continue;
    if (!result || Math.max(...parts) - Math.min(...parts) < Math.max(...result) - Math.min(...result)) {
        result = parts.slice();
    }
}

console.log(result);
console.log(data);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 4

Maras
Maras

Reputation: 982

For each value v in obj o create pair (v, o), then sort all of the pairs by the first element of pair. It takes O(n log n)

Now you want to choose some consecutive elements from the sorted sequence that at least one of every o is inside. You can choose the best answer in O(n log n) (or O(n) using hash map)

Start with choosing the smallest prefix of the sequence that satisfies the condition. Make two pointers, the start of your consecutive chosen elements and the end.

Start = 1, end = x (where x is the smallest value that every object is inside the chosen set)

Then try increasing start (by deleting first element of chosen subsequence) and increase end as long as it's necessary. Take the minimum of the differences between end and start values, it's your answer.

As I said, to keep track if all objects are inside create a map/hash map, where you can store for each object o the amount of it in your chosen sequence. When you increase start you have to decrease the amount of some of the objects inside the subsequence. Then you should increase end until every object o occur nonzero amount of times in the chosen subsequence. (To obtain O(n log n) complexity store how many objects has a value of 0. When you increase any, decrease the counter, when you decrease any object's amount to 0, increase it)

The result is always correct, no heuristics is used.

Upvotes: 4

Related Questions