Javascript Recursion - Cominations up to a value

Question

I'm somewhat new JavaScript, but I'm encountering a scenario where I believe I need to use recursion but I'm not exactly sure how to do it. I have a JavaScript object array that contains about 30 Key-Value pairs per record. What I need to do is loop through all of the records and find all possible combinations where the Total Combined product length is below 2280. After I find each individual combination I want to return the combination of Ship Locations from the object. Any help with this would be much appreciated.

This is what the data looks like that I am trying to find combinations for (there actually about 30 key-value pairs per record, only showing the two related to the question):

 var arr =[{"shipLOC": "ALASTE", "totalProductLength": 480},
            {"shipLOC": "BRONHT", "TotalProductLength": 1520},
            {"shipLOC": "ZIHNER", "TotalProductLength": 120},
            {"shipLOC": "MEADON", "TotalProductLength": 700},
            {"shipLOC": "RUSPOW", "TotalProductLength": 200}]

This code seems to be providing me with all of the combinations that are below the totalTruckLengthAvailable limit of 2280 total length, which is good, but there is additional criteria I need to check before saving the combination and I'm kind of lost on how to do it. There were many combinations of locations provided that may be under 2280 in total length, but still have room for product and could easily use another location to get as close as possible to the 2280 in total length. Is there a way for me to maximize the combinations? Basically I want to keep adding locations while the totalProductLength is below 2280.

function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    
    // There is no way to take e.g. sets of 5 elements from
    // a set of 4.
    if (k > set.length || k <= 0) {
        return [];
    }
    
    // K-sized set has only one K-sized subset.
    if (k == set.length) {
        return [set];
    }
    
    // There is N 1-sized subsets in a N-sized set.
    if (k == 1) {
        combs = [];
    let size = 0;
        for (i = 0; i < set.length; i++) {
      size = size + set[i].attributes.TotalProductLength
            combs.push([set[i]]);
        }
    if (size < totalTruckLengthAvailable){
      return combs;
    } else
        return [];
    }
    
    
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        // head is a list that includes only our current element.
        head = set.slice(i, i + 1);
        // We take smaller combinations from the subsequent elements
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        // For each (k-1)-combination we join it with the current
        // and store it to the set of k-combinations.
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}


function combinations(set) {
    var k, i, combs, k_combs;
    combs = [];
    
    // Calculate all non-empty k-combinations
    for (k = 1; k <= set.length; k++) {
        k_combs = k_combinations(set, k);
        for (i = 0; i < k_combs.length; i++) {
            combs.push(k_combs[i]);
        }
    }
    return combs;
}

console.log(combinations(arr))

The result from the array provided is 8 combinations, as seen in the screenshot below. The problem is that some of these combinations need to be removed as they still have room for more product.

Results

Answer 1

A solution

I feel as though this must be a well-known problem for those who know their computer science algorithms well. But I didn't find it in a quick search.

I have a solution that seems to work. It runs in 50-100 ms on my machine for 30 records that try to look about like your sample, generating a collection of just over 15K sets of values, each of which sums to no more than 2280. Note that the browser will time out if you ask the SO console to format the entire result, but JSON.stringify seems to work, if slowly. Here's the code:

const sum = (ns) => ns .reduce ((a, b) => a + b, 0)

const combsUpTo = (fn) => (t, [x, ...xs], cs = []) => 
  t == 0
    ? [cs]
  : x == undefined
    ? []
  : fn (x) + sum (xs .map (fn)) <= t
    ? [[...cs, x, ...xs]]
  : [
      ... (fn (x) <= t ? combsUpTo (fn) (t - fn (x), xs, [...cs, x]) : []),
      ... (combsUpTo (fn) (t, xs, cs))
    ]

const problem = (total, records) => 
  combsUpTo (x => x .TotalProductLength)
    (total, records .sort ((a, b) => b .TotalProductLength - a .TotalProductLength))

const records = [{"shipLOC": "ALASTE", "TotalProductLength": 480}, {"shipLOC": "BRONHT", "TotalProductLength": 1520}, {"shipLOC": "ZIHNER", "TotalProductLength": 120}, {"shipLOC": "MEADON", "TotalProductLength": 700}, {"shipLOC": "RUSPOW", "TotalProductLength": 200}, {"shipLOC": "FOOBAR", "TotalProductLength": 250}, {"shipLOC": "BAZBAR", "TotalProductLength": 740}, {"shipLOC": "BAZQUX", "TotalProductLength": 620}, {"shipLOC": "FOOQUX", "TotalProductLength": 1380}, {"shipLOC": "CORGE1", "TotalProductLength": 1280}, {"shipLOC": "GRAULT", "TotalProductLength": 370}, {"shipLOC": "BARBAZ", "TotalProductLength": 260}, {"shipLOC": "QUXBAZ", "TotalProductLength": 140}, {"shipLOC": "WALDO1", "TotalProductLength": 830}, {"shipLOC": "QUXQUX", "TotalProductLength": 820}, {"shipLOC": "FOOFOO", "TotalProductLength": 450}, {"shipLOC": "BARFOO", "TotalProductLength": 540}, {"shipLOC": "WALDO1", "TotalProductLength": 570}, {"shipLOC": "QUXBAZ", "TotalProductLength": 330}, {"shipLOC": "CORGE2", "TotalProductLength": 410}, {"shipLOC": "BAZQUX", "TotalProductLength": 970}, {"shipLOC": "GRIOLT", "TotalProductLength": 600}, {"shipLOC": "BARBAR", "TotalProductLength": 320}, {"shipLOC": "BARFOO", "TotalProductLength": 1470}, {"shipLOC": "WALDO2", "TotalProductLength": 150}, {"shipLOC": "GRAWPY", "TotalProductLength": 380}, {"shipLOC": "GRAFOO", "TotalProductLength": 790}, {"shipLOC": "BAZGRI", "TotalProductLength": 910}, {"shipLOC": "CORGI3", "TotalProductLength": 220}, {"shipLOC": "ALAZIH", "TotalProductLength": 450}]

console .time ('Run time')
const results = problem (2280, records)
console .timeEnd ('Run time')
console .log (`Result count: ${results.length}`);
console .log (`Results:`)
console .log (JSON .stringify (results, null, 4))

.as-console-wrapper {max-height: 100% !important; top: 0}

Developing the solution

It took a while to find a way to handle this that didn't need to check whether various solutions were subsets of one another. I ended up finding this technique, where, this syntax:

[5]-{4321}=>3

means that I have already decided to include the value 5, and need to total up to 3 more, using some subset of {4, 3, 2, 1}.

Here we solve for a total of 8 from the values {7, 6, 5, 4, 3, 2, 1}:

                []-{7654321}=>8
                       |
                       |
       +---------------+------------------+
       |                                  |
[7]-{654311}=>1                    []-{654321}=>8
       |                                  |
       |                 +----------------+----------------------+
       |                 |                                       |
[7]-{54321}=>1    [6]-{54321}=>2                           []-{54321}=>8
       |                 |                                       |
       |                 |                      +----------------+-----------------+
       |                 |                      |                                  |
 [7]-{4321}=>1    [6]-{4321}=>2           5]-{4321}=>3                       []-{4321}=>8
       |                 |                      |                                  |
       |                 |                      |                          +-------+-------+
       |                 |                      |                          |               |
 [7]-{321}=>1      [6]-{321]=>2           [5]-{321}=>3                [4]-{321}=>4    []-{321}=>8
       |                 |                      |                          |               |
       |                 |               +------+-------+           +------+-------+       |
       |                 |               |              |           |              |       |
  [7]-{21}=>1      [6]-{21}=>2     [53]-{21}=>0   [5]-{21}=>3  [43]-{21}=>1   4-{21}=>4  [321]
       |                 |               |              |           |              |
       |          +------+-----+         |              |           |              |
       |          |            |         |              |           |              |
  [7]-{1}=>1  [62]-{1}=>0  [6]-{1}=>2  [53]          [521]     [43]-{1}=>1       [421]
       |          |            |                                    |
       |          |            |                                    |
       |          |            |                                    |
      [71]      [62]         [61]                                 [431]


//   [[7, 1],  [6, 2],      [6, 1],    [5, 3],      [5, 2, 1],  [4, 3, 1],   [4, 2, 1], [3, 2, 1]]

The basic algorithm works on a target total and a set of numbers, sorted descending. It looks like this:

const combsUpTo = (t, [x, ...xs], cs = []) => 
  t == 0
    ? [cs]
  : x == undefined
    ? []
  : x + sum (xs) <= t
    ? [[...cs, x, ...xs]]
  : [
      ... (x <= t ? combsUpTo (t - x, xs, [...cs, x]) : []),
      ... (combsUpTo (t, xs, cs))
    ]

combsUpTo (8, [7, 6, 5, 4, 3, 2, 1])
//=> [[7, 1], [6, 2], [6, 1], [5, 3], [5, 2, 1], [4, 3, 1], [4, 2, 1], [3, 2, 1]]

First we check if our total (t) is zero, and if so, we return the chosen values (cs). Second, if our list of numbers is empty (x == undefined`), we return the empty array. Third, if the sum of the remaining numbers is less than or equal to our target, we include the already chosen values and all the remaining elements. Finally, if none of that is true, we potentially split into two paths. The second path we always try, skipping the first number in the list and recurring on the same target, the remaining numbers, and the currently chosen values. The first path we only use if the first number is less than the total; then we add that number to the chosen values, and recur on the remaining total and the other numbers.

We update this basic algorithm so that it can handle items that have numeric values, not just the numbers themselves by adding a fn parameter we will use to extract the numeric summing value from our item. That gives the code in the snippet.

Optimaztions

There are several potential inefficiencies here. We map and sum on every iteration that doesn't bottom out in one of our base cases, and we calculate fn (x) up to three separate times. We could address these, and speed things up. In fact, I wrote this version to address the first problem:

const combsUpTo = (fn) => (t, [x, ...xs], cs = [], s = fn (x) + sum (xs .map (fn))) => 
  t == 0
    ? [cs]
  : x == undefined
    ? []
  : s <= t
    ? [[...cs, x, ...xs]]
  : [
      ... (fn (x) <= t ? combsUpTo (fn) (t - fn (x), xs, [...cs, x], s - fn (x)) : []),
      ... (combsUpTo (fn) (t, xs, cs, s - fn (x)))
    ]

Here we track also s, the sum of the values of our items, subtracting from it on each recurrence the value of our current element, whether we use it or decide to skip it.

But this seems to have been a case of premature optimization, cutting the time by maybe 15%, at the cost of code complexity. I'm guessing that solving the other problem would help even less. So, unless the time is critical, I would likely stick with the simpler version above.

---

This was quite a fun problem. If someone knows if this is in the literature, please comment. I'd love to see how much better a solution academics might have created.