CODEWITHSUNDEEP
javascript
Renu Thakur
Renu Thakur

Reputation: 551

Compute the shortest path going through three arrays

I have three arrays or it may be n. let us take three now. They have values like these:-

Array1=[143, 181];
Array2=[41, 153, 241];
Array3=[22, 67, 131, 190];

I want to find those elements of these three array, Who has minimum difference. Like in this case 143,153,131 has minimum difference.

Upvotes: 4

Views: 180

Answers (2)

pid
pid

Reputation: 11597

Maybe I understood what you want.

You must explore a tree where each array is the list of all descendants of each node, like this:

          * (root)
       /      \
   143          181
  / | \        / | \
41 153 241   41 153 241
/|\/|\ /|\   /|\/|\ /|\
........ descendants from 3rd array

You can then compute the leaves weights as the difference of the ancestor nodes path to that leaf.

Then you want to find the minimum weight of all leaf nodes.

That's not too difficult if you implement it recursively and keep a variable minSoFar and a copy of the nodes to keep the minimum found at any leaf in the tree.

Once this abstract data structure is conceptually clear, the implementation is straightforward and trivial.

EDIT: This implementation has a small memory footprint (just the call stack) and should perform on the same order of complexity as the non-recursive version. In both, recursive and non-recursive implementations shown on this page the complexity is dictated by the abstract data structure. Because of the small memory footprint it should be possible to compute pretty deep structures (many arrays) albeit computation time grows exponentially.

function recursiveMinDiff(arrays)
{
  var minSoFar, minNodes;

  function computeMinDiff(values)
  {
    var i, vs, total;

    vs = values.slice();
    vs.sort(function (a,b) {      // ascending order
      return a - b;
    });

    total = 0;
    for (i = 0; i < vs.length - 1; i++)
    {
      total += vs[i + 1] - vs[i]; // always non-negative
    }

    return total;
  }

  function mindiff(arrays, stack)
  {
    var i, diff, level;

    level = stack.length;
    if (level === arrays.length)  // this is a leaf
    {
      diff = computeMinDiff(stack);
      if (diff < minSoFar)
      {
        minSoFar = diff;          // side-effect on min*
        minNodes = stack.slice(); // clone array
      }
      return;
    }

    for (i = 0; i < arrays[level].length; i++)
    {
      stack.push(arrays[level][i]);
      mindiff(arrays, stack);
      stack.pop();
    }
  }

  minSoFar = Number.MAX_VALUE;
  minNodes = [];
  mindiff(arrays, []);

  return minNodes;
}

Upvotes: 0

Denys S&#233;guret
Denys S&#233;guret

Reputation: 382092

Assuming you don't have a big number of arrays, here's a solution, computing (and storing) all paths:

// First let's use a sensible structure
var arrays = [Array1, Array2, Array3];

// Then, let's compute all possible paths
var paths = arrays[0].map(function(v){ return [v] });
for (var i = 1; i<arrays.length; i++) {
   var arr = arrays[i];
   for (var j=paths.length; j--; ) {
      var newPaths = arr.map(function(v){
        return paths[j].concat(v);
      })
      newPaths.unshift(j,1);
      [].splice.apply(paths, newPaths);
   }
}

// Now, let's just take the shortest one
var shortestDistance = Infinity,
    shortestPath = null;
paths.forEach(function(path){
  var distance = 0;
  for (var i=1; i<path.length; i++) {
    distance += Math.abs(path[i]-path[i-1]);
  }
  if (distance<shortestDistance) {
    shortestDistance = distance;
    shortestPath = path;
  }
});

// Finally, let's log the result
console.log(shortestDistance, shortestPath);

It logs

32
[143, 153, 131]

Upvotes: 3

Related Questions