C# Algorithms – Finding All Combinations with Constraints

algorithmsc

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.

Best Answer

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.

Related Solutions

Algorithms – Compute k-Permutation Without Repeating and No Duplicates

Unless I'm mistaken:

There are 20^5 = 3,200,000 ways to pick 5 numbers out of 20 (with repeating, with duplicates)
If you don't allow for "duplicates" (picking the same number more than once), you're left with n! / (n - k)!, in this case 20! / (20 - 5)! = 1,860,480. These are k-permutations.
If, then, you don't allow for "repeating" (having collections with the same elements only in a different order), you're left with n! / ((n - k)! * k!), in this case 20! / ((20 - 5)! * 5!) = 15,504. These are called k-combinations. These are what you seem to be looking for.

If you are only looking for combinations of size 5 and want access to the entire set of combinations immediately, then I'd say then 5 nested loop approach is fine, and I don't think you'll be able to do anything faster. You just need to modify your idea a bit so you wont need to check for uniqueness or duplicate numbers and don't do unnecessary iterations. You can produce (only) ordered combinations by doing something like:

public Set<Set<Integer>> all5CombinationsOf20(){
    Set<Set<Integer>> result = new HashSet<Set<Integer>>();
    for(int i = 1; i <= 16; i++){
        for(int j = i+1; j <= 17; j++){
            for(int k = j+1; k <= 18; k++){
                for(int l = k+1; l <= 19; l++){
                    for(int m = l+1; m <= 20; m++){
                        result.add(new HashSet<Integer>(Arrays.asList(i,j,k,l,m)));
                    }
                }
            }
        }
    }
    return result;
}

Since this gives you the combinations in a ordered way [1, 2, 3, 4, 5] is produced, but [3, 2, 1, 5, 4] and [1, 1, 2, 3, 4] are not.

However this approach is not extendable to combinations of arbitrary size, then you would need recursion. I once wrote this:

public static <T> Set<Set<T>> combinations(Set<T> alphabet, int k) {
    if (alphabet.size() == 0) {
        throw new IllegalArgumentException("alphabet.size must be > 0");
    }
    if (k < 0) {
        throw new IllegalArgumentException("k must be >= 0");
    }
    if (k == 0) {
        Set<Set<T>> result = new HashSet<Set<T>>();
        result.add(new HashSet<T>());
        return result;
    } else {
        Set<Set<T>> result = new HashSet<Set<T>>();
        for (T e : alphabet) {
            Set<T> newAlphabet = new HashSet<T>(alphabet);
            newAlphabet.remove(e);
            Set<Set<T>> smallerCombinations = combinations(newAlphabet, k - 1);
            for (Set<T> smallerCombination : smallerCombinations) {
                Set<T> combination = new HashSet<T>(smallerCombination);
                combination.add(e);
                result.add(combination);
            }
        }

        return result;
    }
}

This is not necessarily fast since you are messing around the alphabet a lot, but the idea should be clear: to make a combination of size n over a certain alphabet (in your case 1..20), remove an element e from the alphabet, make a combination of size n-1 over the alphabet minus e and return the combination with e added. Reusing the same alphabet for smaller combinations an letting the HashSet get rid of duplicates would be faster.

Also these sets of combinations get large pretty fast, so you might want to be lazy and not hold them all in memory (depending one how you want to use them), if so, check https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

C# IEnumerable, List, and Arrays – Understanding Unexpected Modifications

Your problem is that you are only returning a single array from your Combinations function, but returning it multiple times with the values changed inside the array between each iteration.

Methods which use yield return are coroutines - in each foreach iteration they execute up to the next yield statement they find and then they exit, picking up where they left off in the next iteration. In your first foreach loop you are taking the enumerated int[] value and putting it into your newL variable - but it's always the same int[] value because Combinations only ever creates one array. The print out in the first foreach works fine because the coroutine is paused waiting for the next iteration to start.

You have a couple of options. The best option is to make your Combinations have a sane implementation, in that it returns a new object for each yield return statement. That might look something like this:

    public static IEnumerable<int[]> Combinations(int m, int n)
    {
        while (weStillHaveMoreResultsToBuild)
        {
            int[] result = new int[m];

            while (value < n)
            {
                // fill result and break out of loop when done
            }

            yield return result;
        }
    }

Another option would be to not use yield return at all, and instead build a list inside Combinations and return that. This approach could take a lot more memory if your n and m values are large.

A third option is to make a copy of the objects returned by Combinations and store those instead:

newL.Add(combs.ToArray()); // Calling ToArray() will make a copy

This is my least favorite option, because it requires any caller of Combinations to know that the same object will be returned multiple times but changed in each iteration.

Best Answer

Related Solutions

Algorithms – Compute k-Permutation Without Repeating and No Duplicates

C# IEnumerable, List, and Arrays – Understanding Unexpected Modifications

Related Topic