javascriptarraysmultidimensional-arrayhungarian-algorithm

What do I need to know about creating a list of ranked pathways from 2D array?


Suppose I have a matrix of equipment and their stats. Hats, shirts, pants, boots. Each inner-array can vary in size, but there's always going to be a set amount of the inner-arrays - in this case 4.

var array = [
  [1,9,2,8,3],        // hat
  [2,8,3,6],          // shirt
  [1,3],              // pants
  [9,3,2,6,8,2,1,5,2] // boots
]

I want to find the optimal pathway through the matrix, then remove an item in such a way that the next route (and therefore sum of the route) determined is the next-best following the first. In this example, [9, 8, 3, 9] would be best, correct? So we can remove a 9 in [0] to reach 8 giving a drop of only 1.

I could sum all the possible routes and determine it from there but the size of the inner-arrays could be much bigger than shown.

I've spent some time thinking about it, and researched around. The only thing I can see is the Hungarian Algorithm but it stretches past my maths/compsci knowledge right now. Would that be the most applicable knowledge in this case? It seems to cater for the lowest possible 'cost' of a route but I need the opposite.

My idea, at least as a thought:

  1. Pull the highest number in each inner-array, create new array from those. Rank this [0].
  2. Compare the highest number in each inner-array with the next lowest. Order the differences between each one.
  3. Remove the highest number from the inner-array with the lowest difference found in #2.
  4. Repeat #1 through #3.

In the example above, I would expect something like below.

[9, 8, 3, 9]
[8, 8, 3, 9]
[8, 8, 3, 8]
[8, 6, 3, 8]
[8, 6, 3, 6]
[8, 6, 3, 5]

EDIT: I think I butchered the explanation for this problem, let me fix it up a bit.

EDIT2: Essentially the minimum-loss across sets, removing only one item from only one inner-array.


Solution

  • UPDATE: I originally misinterpreted your question. You subsequently clarified the question, and I provide here a completely new solution.

    The strategy I use is to flatten all the elements in all sub-arrays into a single array but do so in a way that remembers which original sub-array they come from. I then sort the flattened array, first by value in descending order, then by sub-array number in ascending order. For example, the 1st 3 elements of the sorted flattened array would be [[9,0], [9,3], [8,0],...] representing the value 9 from sub-array 0, then value 9 from sub-array 3, then value 8 from sub-array 0, etc. I then proceed through the list, taking as many values as I need until I reach n, but leaving room for any sub-arrays for which I have not yet chosen a value.

    Note that this solution works for any number of sub-arrays each with any number of elements.

    const array = [
      [1,9,2,8,3],        // hat
      [2,8,3,6],          // shirt
      [1,3],              // pants
      [9,3,2,6,8,2,1,5,2] // boots
    ];
    for (let n = 0; n < 17; n += 1) {
      const valuesChosen = getTopNBest(array, n);
      console.log(`n = ${n}: ${JSON.stringify(valuesChosen)}`);
    }
    
    function getTopNBest(array, n) {
      const numTypes = array.length;
      const allElmtsRanked = [];
      array.forEach((sub, typeNum) => {
        sub.forEach(elmt => {allElmtsRanked.push([elmt, typeNum]);});
      });
      allElmtsRanked.sort((a,b) => b[0] - a[0] !== 0 ? b[0] - a[0] : a[1] - b[1]);
      const valuesChosen = array.map(() => null);
      let totalNumValuesExamined = 0;
      let numSecondaryValuesChosen = 0;
      let numUnrepresentedTypes = numTypes;
      let currPair, currValue, currTypeNum;
      while (numUnrepresentedTypes !== 0 || numSecondaryValuesChosen < n) {
        currPair = allElmtsRanked[totalNumValuesExamined];
        currValue = currPair[0];
        currTypeNum = currPair[1];
        totalNumValuesExamined += 1;
        if (valuesChosen[currTypeNum] === null) {
          valuesChosen[currTypeNum] = currValue;
          numUnrepresentedTypes -= 1;
        } else if (numSecondaryValuesChosen < n) {
          numSecondaryValuesChosen += 1;
          valuesChosen[currTypeNum] = currValue;
        }
      }
      return valuesChosen;
    }

    You subsequently asked why I sorted first by value then by sub-array number. Compare the following two scenarios:

    var array = [
      [8],
      [9,9,9,9,9],
      [8],
      [8]
    ]
    

    ...versus...

    var array = [
      [9,8],
      [9,9],
      [9,8],
      [9,8]
    ]
    

    If you simply flattened these and sorted the flattened array without retaining any information about which sub-array the values came from, you'd end up with the same sorted flattened array in both cases, i.e.

    var sortedFlattenedArray = [9,9,9,9,9,8,8,8]
    

    Let's say you want the best/most optimal pathway. You'd now get [9,9,9,9] with either scenario whereas with the first scenario you really want [8,9,8,8]. You can only get this when you've remembered the sub-array/type number, e.g.:

    var sortedFlattenedArray = [[9,1],[9,1],[9,1],[9,1],[9,1],[8,0],[8,2],[8,3]]
    

    The actual strategy thus allows you to ignore reasonably-high-but-sub-optimal values from already sampled types when you no longer want any more sub-optimal values for any type but you're still looking for the highest possible value for a particular type.

    Here's another way of looking at it. The strategy here allows you to flatten and sort all the original arrays but remember where each element came from. This in turn allows you to be selective when choosing a pathway by saying, "Ah, the next value is pretty high, which is good, but wait, it's for a hat (which you could only know by being able to read it's associated sub-array/type number) and I've already retrieved my quota of 'sub-optimal values', so I'll ignore this hat value. However, I'll keep moving through the sorted flattened array to find highest remaining value for a shirt (which, again, you could only discover by being able to read its associated sub-array/type number) for which I still haven't yet found any value."