Permutations from JSON time value in JavaScript

Question

Lets say that I have a JSON file as such:

 {
"item1":{"time":"00:18:21"},
"item2":{"time":"00:22:22"},
"item3":{"time":"00:02:11"},
"item4":{"time":"01:34:32"}
}

How would I go about finding all possible values of item combination time sums that exist between lets say 00:03:04 to 00:25:55 without finding every single permutation combination that exists and adding them for that set? ex item 1 and item 3 would be found in that time constraint where their times add together to 00:20:32. I have tried to use permutations, but you run into certain drawbacks with more objects. If I go up to 7 objects, it clearly takes me over 13,000 iterations of adding time values together and checking for range constraints. What can I do to simplify the algorithm?

Edit: (You guys requested some background information) I'm trying to make an application that sorts through a collection of videos with length in hh:mm:ss format and generate a playlist with a given time length.

You question is unclear. Please explain your problem properly — Rajesh, Mar 23 '17 at 05:52
Welcome to Stack Overflow. Could you explain a little more background about why you need to know these "time sums"? — gyre, Mar 23 '17 at 05:52
You should store it as timestamp, and display it in the way you store it. Also, have a check at [date-fns](https://github.com/date-fns/date-fns) and [momentjs](https://momentjs.com/), theses lib allow you tu easely manipulate dates. — Dimitri Kopriwa, Mar 23 '17 at 05:58
@gyre I tried my best to explain my full problem through the edit. — woisinthis, Mar 23 '17 at 06:07
@guest271314 Yes if you think of it that way, but the time added together of multiple objects must be within the constraint. — woisinthis, Mar 23 '17 at 06:13
@guest271314 it would be pointless. I simply loop through all the possible combinations/permutations, create an array for each of the variation, add all the time values in the array, and sort those arrays against the constraint. ( I also don't have my code right now. ) — woisinthis, Mar 23 '17 at 06:26
So you want to find all possible combinations that are within the time constraint? You don't want to find one, you want to find all of them? — Vic, Mar 23 '17 at 06:28
@vic Yes, but the method I used has way too much going on at once.I'm trying to find logic for a smaller, lighter method. — woisinthis, Mar 23 '17 at 06:31
@woisthis I'm assuming you convert these time codes into numbers, right? You might find a proper algorithm in the area of `Dynamic Programming`, by the way. I'm figuring it out myself, seems pretty interesting. — Vic, Mar 23 '17 at 06:33
@Vic yes, in my original algorithm I added them by converting them to seconds, then back. Dynamic Programming does seem pretty cool on the other hand. — woisinthis, Mar 23 '17 at 06:35
@woisthis Took it as an elective. It was a nasty experience, but whenever something looks like a DP problem, at least I know where to go. Another helpful keyword for you (which seems VERY relevant) is `memoization`. https://en.wikipedia.org/wiki/Memoization Not sure if it's a subset of DP, but sure was a subset in my elective. Oh, how could I forget `tabulation`! Also a seemingly relevant topic for you. http://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming — Vic, Mar 23 '17 at 06:39
@vic thank you this is something I will look into. I'm guessing there is no easy solution. — woisinthis, Mar 23 '17 at 06:43

score 0 · Accepted Answer · answered Mar 23 '17 at 07:44

You could get all combinations an check if a combination fits into the given interval. Then push it to the result array.

function getCombinations(object, min, max) {

    function getTotalTime(a) {
        return a.map(a => getTimeValue(object[a].time)).reduce((a, b) => a + b, 0);
    }

    function getTimeValue(t) {
        return t.split(':').reduce(function (a, b) { return a * 60 + +b; });
    }

    function getTimeString(v) {
        return [60, 60, 1].map(t => [v % t, v = Math.floor(v / t)][0]).map(a => ('00' + a).slice(-2)).reverse().join(':');
    }

    function fork(i, t) {
        var total = getTotalTime(t);
        if (i === array.length) {
            if (minValue <= total && total <= maxValue) {
                result.push({ keys: t, time: getTimeString(total) });
            }
            return;
        }

        fork(i + 1, t.concat(array[i]));
        fork(i + 1, t);
    }

    var result = [],
        minValue = getTimeValue(min),
        maxValue = getTimeValue(max),
        array = Object.keys(object);

    fork(0, []);
    return result;
}

var data = { item1: { time: "00:18:21" }, item2: { time: "00:22:22" }, item3: { time: "00:02:11" }, item4: { time: "01:34:32" } },
    result = getCombinations(data, '00:03:04', '00:25:55');

console.log(result);

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

Thank you very much! This is way more efficient than my current method. What was your thought process in this? — woisinthis, Mar 23 '17 at 19:52
it follows the idea to generate all binary numbers for a given length, where 1/0 itself is representing an item or not and the length is the length of the given array. in this case, the algorithm generates 2^4 diffferent results and tests against the interval. — Nina Scholz, Mar 23 '17 at 21:53

Permutations from JSON time value in JavaScript

1 Answers1