2

I'm looking for a way in C# that finds all the possible combinations with constraints.

I've got a list of machines. The machines have capabilities and limitations. I also have a document that defines the starting material and end result.

The machine capabilities is a flag enum with cut, print, joint. Constraints are specific to the capability of the machine. Constraint for cut example would be length/width of the starting material. print would be the number of different print patterns that can be done at once. Joint constraint is a list of GUIDs that refer to a joint object. if the machine has the joint GUID declared in the product document in it's list of joints it is capable of, then the machine should be selected as an option.

currently I've got functions that finds machines for each operation out of all the machines. I then intersect (linq intersect) the 3 lists (one list for each capability), and that produces my list of capable all-in-one machines.

but with these three lists, I now need to find all the combinations going from cut to print to joint. each combination goes into a flow object that represents this combination. basically a name and the list of machines in order.

As another wrench, the printing doesn't always happen.

Can someone help me finding or devising a solution for this please?

Edit for example:

lets say I have 6 machines. 3 that cut, 1 that prints, 2 that joints. I need to create a list for each possible combination that has 1 cut machine, 1 print machine, and 1 joint machine.

the desired outcome here would be:

{cut1, print1, joint1},
{cut1, print1, joint2},
{cut2, print1, joint1},
{cut2, print1, joint2},
{cut3, print1, joint1},
{cut3, print1, joint2}

sometimes, the provided instructions (document that defines the starting material and product size) don't call for printing. When this happens, using the same 6 machines, I need to create a list for each possible combination for 1 cut machine and 1 joint machine.

the desired outcome for this would be:

{cut1, joint1},
{cut1, joint2},
{cut2, joint1},
{cut2, joint2},
{cut3, joint1},
{cut3, joint2}

I've figured out how to filter out machines that don't have the capabilities defined in the instructions document and put those into list of capable cut/print/joint machines. Now i just need to find all the possible permutations of these three list, where each permutation includes one item from each list.

2
  • so i'm relegated to nested foreach loops. there's not something like this answer on SO stackoverflow.com/questions/7802822/… that allows the addition of constraints or have the linq call functions or something
    – xtreampb
    Jan 31 at 18:29
  • Yea, i was thinking that there were other solutions that might have this solved differently. but it really is just triple nested foreach loops. just pre-filter out the machines into lists and iterate on them all.
    – xtreampb
    Feb 2 at 15:41

1 Answer 1

2

This sounds like the kind of problem that would be straightforward to brute force, but if that leads to unmanageable combinatorial expansion, it will use some clever tricks to signficantly suppress the amount of combinations that are attempted. However, that cleverness is highly contextual to a point of needing to individually analyze cost, complexity and benefit.

This answer can only do the non-contextual bit. It's always possible that you can optimize this even further with clever tricks that require more specialized knowledge.

lets say I have 6 machines. 3 that cut, 1 that prints, 2 that joints. I need to create a list for each possible combination that has 1 cut machine, 1 print machine, and 1 joint machine.

The straightforward solution here is nesting your loops:

var cutters = GetCutters();
var printers = GetPrinters();
var joiners = GetJoiners();
var result = new List<Combination>();

foreach(var cutter in cutters)
  foreach(var printer in printers)
    foreach(var joiner in joiners)
      result.Add(new Combination(cutter, printer, joiner));

sometimes, the provided instructions (document that defines the starting material and product size) don't call for printing. When this happens, using the same 6 machines, I need to create a list for each possible combination for 1 cut machine and 1 joint machine

The one caveat here is that the above example cannot handle empty lists. If there are no printers, for example, you'd expect it to return all combinations or cutters and joiners, which it won't do.

You could come up with a dynamic solution that takes in an arbitrary amount of lists, but this very quickly becomes very abstract and complex, on top of needing some clever work with generics to make it work (assuming your different machines are represented using different types).

There are two more straightforward solutions here, both of which could be done with the hardcoded loops like the above example:

Option 1 - filter it afterwards. Generate every combination and then filter out the ones you don't need, e.g.

var result = ...; // the above code

// Example 1: removing one of many options
result = result.Where(c => c.Cutter != theCutterWeDontWantToUse);

// Example 2: ignoring one of the machine types entirely
result = result
           .GroupBy(c => new { c.Cutter, c.Joiner }) // only look at distinct cutter/joiner combinations
           .Select(group => group.First())           // pick the first from each group

Option 2 - If a list is intentionally empty (i.e. you don't want to use any printer), instead of setting it to an empty list, make it a list with a single null entry.

var cutters = GetCutters();
var printers = GetPrinters();
var joiners = GetJoiners();
var result = new List<Combination>();

if(!cutters.Any())
  cutters = new List<Cutter>() { null };

if(!printers.Any())
  printers = new List<Printer>() { null };

if(!joiners.Any())
  joiners = new List<Joiner>() { null };

foreach(var cutter in cutters)
  foreach(var printer in printers)
    foreach(var joiner in joiners)
      result.Add(new Combination(cutter, printer, joiner));

This does mean having to account for null values, but depending on your surrounding context it may already have been obvious that the Combination.Printer property would never be used anyway (at which point you might not need to explicitly safeguard against a null value here).

These two options might not be the most elegant; but given the increased complexity of doing it the dynamic way, it's fairly likely that these options are better on a cost-benefit scale.

7
  • 1
    Rather than accounting for null values consider null objects. The empty string can be a powerful tool. Feb 1 at 2:01
  • 1
    @candied_orange: Definitely a good additional tip, I was weary of including it in the "core" answer because not all classes have an obvious null-value-object.
    – Flater
    Feb 1 at 2:06
  • Really? Thought we just wanted a way to suppress print1, whenever we felt like it. Feb 1 at 2:11
  • @candied_orange: The reason I'm trying to strike a balance here rather than doing it the fully-engineered and complete way is because of the significant spike in complexity when doing so. This is one of those cases where complexity can fairly quickly spiral out of control. Additional improvements aren't wrong, but it's more difficult to judge whether their added complexity is worth what it actually brings to the table.
    – Flater
    Feb 1 at 2:15
  • Flater the joy of using null objects is they don't add complexity. They sneak into your existing code that breaks when you feed it a null and instead, when your code demands something it provides that something. It's just a something that does nothing. Feb 1 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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