0

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 Mar 23 '17 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 Mar 23 '17 at 13:41
  • I've read this 4 times and still don't understand what is being asked. – whatsisname Mar 23 '17 at 23:29
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.

  • 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 Mar 23 '17 at 15:32
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.