# Eliminating combinations based on user input

I am stuck with this particular problem. To give context to the problem, I am developing a mobile app which helps with loading dangerous goods onto a truck. Ignore the size and weight of the dangerous goods.

Some dangerous goods cannot be loaded onto a truck unless one of the goods is in a specific type of box.

For example, Flammable Liquid and Oxidizer cannot be placed together in a truck unless one of them is in a specific type of box. So you can choose one of those goods to be in a box.

My problem is when we have multiple cases of these scenarios, for example:

• Flammable Liquid and Oxidizer cannot be placed together unless one is in a box

• Flammable Liquid and Organic Peroxide cannot be placed together unless one is in a box

• Dangerous When Wet and Organic Peroxide cannot be placed together unless one is in a box

• Dangerous When Wet and Oxidizer cannot be placed together unless one is in a box

• Oxidizer and Organic Peroxide cannot be placed together unless one is in a box

If a combination of goods is not listed, then assume that they can be placed together. For example, there is no combination of Flammable Liquid and Dangerous When Wet. This means that they can be put together regardless of being in a box or not. The above combinations means one of them HAS to be in a box.

I need to develop an algorithm to decide which goods need to be in a box so that all those combinations work.

Any help on this would be really appreciated.

• You mentioned a "specific type of box" but never gave any types. Are all boxes used here the same type of box? Commented Oct 3, 2022 at 2:59
• Yes. Same type of box in this case. They are called Segregation Devices to be specific Commented Oct 3, 2022 at 3:17
• Segregation Devices? Seriously? Ow. Commented Oct 3, 2022 at 3:18
• I think your spec misses that you want to minimize number of boxes, I guess? Otherwise you could put every good into a box, which solves what you asked for. Commented Oct 3, 2022 at 5:02
• @candied_orange: a little bit more clarity should not hurt here. Commented Oct 3, 2022 at 5:17

Here is a short outline how to approach this for "not-too-large" number of goods in an optimal manner:

• Start with a configuration of boxes which fulfills all the constraints (but isn't necessarily optimal). You can, for example, start with the good which has the biggest number of "dangerous neighbours" and put it into a box, then look at the remaining goods and repeat the former step until there are no open constraints any more.

• Now, lets say the former step found k boxes for your n goods. Next, you try if k-1 boxes might be sufficient. This can be done brute-force by a standard combinatorical algorithm for generating all combinations of elements of a set of certain size.

If among those combinations you find one which fulfills all contraints, replace k by k-1 and repeat this step, until k cannot decreased any more.

This should work for not too large n and (more important) not too large initial values of k. The number of k-combinations out of n elements can be easily calculated by the binomial coefficient, so once you found an initial start combination, you can calculate the maximum number of iterations required in each step and so estimate your maximum expected running time.

One way to solve this is to treat it like a graph problem:

Which means this:

``````"Flammable Liquid" "Oxidizer"
"Flammable Liquid" "Organic Peroxide"
"Dangerous When Wet" "Organic Peroxide"
"Dangerous When Wet" "Oxidizer"
"Oxidizer" "Organic Peroxide"
``````

Becomes this:

Which makes it obvious that a minimum of two boxes are needed:

All black lines are crossed with red lines. Of course, who wants flammable liquid sloshing around loose in their truck? Especially next to something labeled "Dangerous when wet". The rules might not demand it but I'd spring for the extra box. If you're too cheap to just box them all you might want to keep that last one in the cab, out of the rain.

I need to figure out an algorithm that can decide which goods need to be in a box so all those combinations work.

Haven't tested this but if a greedy algorithm is ok it might be as simple as make each item a collection. Create a `notTogether()` method that takes two of them and places each in the other. Now dump all of them into a priority queue that sorts by collection length.

Collections that contain collections that contain themselves don't support `toString()` very well. Might make debugging easier to have a map of objects to strings to give these things printable names. Or just break down and make a custom `Item` class with it's own `toString()` and backed by a collection. Either way this is a cyclic graph so you need to limit the depth of `toString()` or it'll loop forever.

Create a `box()` function that pops the item with the longest collection off the queue and traverses the rest of the queue removing that item from the others. Soon as the longest collection in the queue is 0 everything that needs boxing is boxed.

Come to think of it, rather than traverse the rest of the queue just visit everything in the collection of whatever you just boxed and once there remove whatever was just boxed.

The collections in the priority queue would look like:

``````Organic Peroxide   (3) Oxidizer, Flammable Liquid, Dangerous When Wet
Oxidizer           (3) Organic Peroxide, Flammable Liquid, Dangerous When Wet
Flammable Liquid   (2) Organic Peroxide, Oxidizer
Dangerous When Wet (2) Organic Peroxide, Oxidizer
``````

`box( pq.pull() )` will box Organic Peroxide and it becomes

``````Oxidizer           (2) Flammable Liquid, Dangerous When Wet
Flammable Liquid   (1) Oxidizer
Dangerous When Wet (1) Oxidizer
``````

`box( pq.pull() )` will box Oxidizer and you're done

``````Flammable Liquid   (0)
Dangerous When Wet (0)
``````

Leaving those two together still seems weird.

• Yes boxes are expensive, drivers have a limited number of it. Just to get a better grasp of what you mean. I need to develop an algorithm which can try to see if those " black lines" are all covered with a box perhaps. I can see what you mean and it does give me some sort of direction Commented Oct 3, 2022 at 3:27
• You also might want to consider your liability here. Create an app that teaches people it's ok to store flammable liquid loose in their truck and the fire department isn't going to be happy with you. Commented Oct 3, 2022 at 3:30
• All the legal stuff is sorted :) The environmental section of our government gave us a chart which ensures which goods need to be in an SD. Well yes it won't be "loose". It will be in a container. Just not in a Segregation Device Commented Oct 3, 2022 at 3:31
• Which government is this? I'm actually not sure this question isn't running into the same problem. Commented Oct 3, 2022 at 3:33
• Ack! No. Test at every stage of development. Fail early when your code monkeys still have this stuff in their heads. Commented Oct 3, 2022 at 12:28

Since the number of goods that possibly require boxes seems to be very limited, you might just enumerate all cases, eliminate the invalid ones, and pick any case which requires the smallest number of boxes.

For 5 types of dangerous goods packed into a truck (I suppose that would be a rare case) you have 32 table entries. Not really a hard or time consuming problem for a computer.

Example: Good types A, B, and C. A+B and A+C are dangerous, B+C isn't. You would require 5 boxes to contain A, 2 boxes for B, and one box for C.

All possible combinations with number of required boxes (0 if good isn't boxed in a combination) and validity:

``````A B C valid
0 0 0 no
0 0 1 no
0 2 0 no
0 2 1 yes
5 0 0 yes
5 0 1 yes
5 2 0 yes
5 2 1 yes
``````

Putting B and C in boxes would require the smallest number of boxes (3), so you pick that solution.

• "Good types A, B, and C. A+B and A+C are dangerous, B+C isn't. " Means put A in a box. "5 boxes to contain A, 2 boxes for B, and one box for C." Huh? Where is 5 coming from? Commented Oct 3, 2022 at 15:26
• Arbitrary numbers to show that the minimum number of goods types doesn't necessarily equal minimum number of boxes. If you have a lot of A but relatively little B and C putting A in boxes may consume more boxes than putting both B and C in boxes. Commented Oct 3, 2022 at 18:38
• I don't think that's within the scope of the problem. We're being asked to determine if A needs boxing. Not how many boxes A requires. Commented Oct 3, 2022 at 19:32