Generate all possible coverage options

Question

Suppose I have 2 lists: one containing strings, one containing integers, they differ in length. The application I am building will use these lists to generate combinations of vehicle and coverage areas. Strings represent area names and ints represent vehicle ID's.

My goal is to generate a list of all possible unique combinations used for further investigation. One vehicle can service many areas, but one area can't be served by multiple vehicles. Every area must receive service, and every vehicle must be used.

So to conclude the constraints:

• Every area is used only once
• Every vehicle is used at least once
• No area can be left out.
• No vehicle can be left out

Here is an example:

public class record = {
    public string areaId string{get;set;}
    public int vehicleId int {get;set;}
}

List<string> areas = new List<string>{ "A","B","C","D"};
List<int> vehicles = new List<int>{ 1,2};

List<List<record>> uniqueCombinationLists = retrieveUniqueCombinations(areas,vehicles);

I just have no clue how to make the retrieveUniqueCombinations function. Maybe I am just looking wrong or thinking too hard. I am stuck thinking about massive loops and other brute force approaches. An explanation of a better approach would be much appreciated.

The results should resemble something like this, I think this contains all possibilities for this example.

A1;B1;C1;D2
A1;B1;C2;D1
A1;B2;C1;D1
A2;B1;C1;D1
A2;B2;C2;D1
A2;B2;C1;D2
A2;B1;C2;D2
A1;B2;C2;D2
A2;B1;C1;D2
A1;B2;C2;D1
A2;B2;C1;D1
A1;B1;C2;D2
A2;B1;C2;D1
A1;B2;C1;D2

Answer 1

Here's something I threw together that may or may not work. Borrowing heavily from dtb's work on this answer.

Basically, I generate them all, then remove the ones that don't meet the requirements.

List<string> areas = new List<string> { "A", "B", "C", "D" };
List<int> vehicles = new List<int> { 1, 2 };

var result = retrieveUniqueCombinations(areas, vehicles);
result.ToList().ForEach((recordList) => { 
    recordList.ToList().ForEach((record) => 
        Console.Write("{0}{1};", record.areaId, record.vehicleId)); 
    Console.WriteLine(); 
});

public IEnumerable<IEnumerable<record>> retrieveUniqueCombinations(IEnumerable<string> areas, IEnumerable<int> vehicles)
{
    var items = from a in areas
                from v in vehicles
                select new record { areaId = a, vehicleId = v };
    var result = items.GroupBy(i => i.areaId).CartesianProduct().ToList();
    result.RemoveAll((records) => 
        records.All(record => 
            record.vehicleId == records.First().vehicleId));
    return result;
}

public class record
{
    public string areaId { get; set; }
    public int vehicleId { get; set; }
}


static class Extensions
{
    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
      this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
        return sequences.Aggregate(
          emptyProduct,
          (accumulator, sequence) =>
            from accseq in accumulator
            from item in sequence
            select accseq.Concat(new[] { item }));
    }
}

This produces the following:

A1;B1;C1;D2;
A1;B1;C2;D1;
A1;B1;C2;D2;
A1;B2;C1;D1;
A1;B2;C1;D2;
A1;B2;C2;D1;
A1;B2;C2;D2;
A2;B1;C1;D1;
A2;B1;C1;D2;
A2;B1;C2;D1;
A2;B1;C2;D2;
A2;B2;C1;D1;
A2;B2;C1;D2;
A2;B2;C2;D1;

Note that these are not in the same order as yours, but I'll leave the verification to you. Also, there's likely a better way of doing this (for instance, by putting the logic in the RemoveAll step in the CartesianProduct function), but hey, you get what you pay for ;).

Answer 2

So lets use some helper classes to convert numbers to IEnumerable<int> enumerations in different bases. It may be more efficient to use List<> but since we are trying to use LINQ:

public static IEnumerable<int> LeadingZeros(this IEnumerable<int> digits, int minLength) {
    var dc = digits.Count();
    if (dc < minLength) {
        for (int j1 = 0; j1 < minLength - dc; ++j1)
            yield return 0;
    }
    foreach (var j2 in digits)
        yield return j2;
}

public static IEnumerable<int> ToBase(this int num, int numBase) {
    IEnumerable<int> ToBaseRev(int n, int nb) {
        do {
            yield return n % nb;
            n /= nb;
        } while (n > 0);
    }

    foreach (var n in ToBaseRev(num, numBase).Reverse())
        yield return n;
}

Now we can create an enumeration that lists all the possible answers (and a few extras). I converted the Lists to Arrays for indexing efficiency.

var areas = new List<string> { "A", "B", "C", "D" };
var vehicles = new List<int> { 1, 2 };

var areasArray = areas.ToArray();
var vehiclesArray = vehicles.ToArray();
var numVehicles = vehiclesArray.Length;
var numAreas = areasArray.Length;
var NumberOfCombos = Convert.ToInt32(Math.Pow(numVehicles, numAreas));
var ansMap = Enumerable.Range(0, NumberOfCombos).Select(n => new { n, nd = n.ToBase(numVehicles).LeadingZeros(numAreas)});

Given the enumeration of the possible combinations, we can convert into areas and vehicles and exclude the ones that don't use all vehicles.

var ans = ansMap.Select(nnd => nnd.nd).Select(m => m.Select((d, i) => new { a = areasArray[i], v = vehiclesArray[d] })).Where(avc => avc.Select(av => av.v).Distinct().Count() == numVehicles);