Permutations for time in JSON

Question

Let's say that I have a JSON file like at example below.

How would I go about finding all possible values of item combination time sums that exist between let's say 00:03:04 to 00:25:55 without finding every single permutation combination that exists and adding them for that set?

For example 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?

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

I'm not sure why this is getting downvotes and close votes. Algorithms are clearly on topic here. — Karl Bielefeldt
– Karl Bielefeldt, Commented Mar 23, 2017 at 12:58
@KarlBielefeldt this is possibly because question was rather poorly laid out. Original version looked like a code dump followed by hard to read wall of text. I edited it to hopefully better shape — gnat
– gnat, Commented Mar 23, 2017 at 13:41
I've read this 4 times and still don't understand what is being asked. — whatsisname
– whatsisname, Commented Mar 23, 2017 at 23:29

Karl Bielefeldt · Accepted Answer · 2017-03-23 13:30:21Z

0

Mostly where you're going wrong is finding permutations when you only need to look for combinations. For your example, if item 1 and item 3 are found, you don't need to check later for item 3 and item 1, but your 13,000 number shows that you are. If you eliminate those duplicate checks, there are only 120 combinations to check for 7 objects.

You can also look for opportunities for pruning. If item 1 + item 2 is greater than your max range, you don't need to check item 1 + item 2 + item 3, item 1 + item 2 + item 4, and so forth. If you arrange your checks depth-first, it will be easiest to do this pruning.

answered Mar 23, 2017 at 13:30

Karl Bielefeldt

149k38 gold badges285 silver badges485 bronze badges

It might be worth saying that this is pretty much what constraint programming libraries do. You model your problem with constraints (and this one is quite easy to do), and you feed it to a solver.

Vincent Savard
– Vincent Savard

2017-03-23 15:32:57 +00:00
Commented Mar 23, 2017 at 15:32

Add a comment |

gnasher729 · Accepted Answer · 2017-03-23 21:44:44Z

The problem has nothing to do with JSON, unless extracting a few numbers from JSON into an array is a problem for you.

You don't need permutations of the times, you need a subset. In your example of 7 time values, there are 128 possible subsets of these values. So the problem can easily be solved in O (2^n) where n is the number of values; faster if the target time is so small that you only need to consider subsets with few items.

An alternative is an algorithm which takes about O (k), where k is the target time, which will be better if k is small compared to 2^n: Create a bitmap of all totals that can be created using any subset of the first 1, 2, 3, ... items.

Stack Exchange Network

Permutations for time in JSON

2 Answers 2

Your Answer

Hot Network Questions

Permutations for time in JSON

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions