Algorithm for finding all combinations with constraints

Question

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.

Answer 1

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.