How to get all combinations of several List

Question

Differs from sugested solution above in that a list item can only appear once for each row.

This is for a booking system for my spa. Different employees can perform different treatments.

I have a List<List<int>>. These are therapists that can perform the treatment that is booked.

Each list (booking) contain a number of integers like this (these are therapists that can perform the booking):

{1, 3, 6},  //Booking 1
{1, 2, 6},  //Booking 2
{1},        //Booking 3
{2,3}       //Booking 4

I'd like to see all possible combinations where the number can only appear in one Place. For the above list the two possible ombinations would be:

6,2,1,3 or 3,6,1,2

That is for the first combination:

Booking 1: Therapist 6
Booking 2: Therapist 2
Booking 3: Therapist 1
Booking 4: Therapist 3

Hope this makes the question a Little bit clearer.

No, In that question the numbers can be in several places. So all combinations would be acceptable there. — ekenman, Jul 14 '13 at 17:34
The question doesn't make sense. The solution appears to be solvable by Distinct() but where does the order fit in? — Gayot Fow, Jul 14 '13 at 17:35
@Garry Vass The order of each result element is the order of the list where they're selected. i.e. 1st element must be picked from the 1st list, and once that number is picked, you can no longer pick it from following lists. — Fung, Jul 14 '13 at 17:42
@ekemann: Must every list assign exactly one integer? Are all lists ordered by default? — Tim Schmelter, Jul 14 '13 at 17:44
@TimSchmelter Yes. Hope the question makes a Little bit more sense now. — ekenman, Jul 14 '13 at 17:49
@Prix I guess I could use that solution and then remove the ones I can't use even though it is not very elegant. Thanks! — ekenman, Jul 14 '13 at 18:02

Fung · Answer 1 · 2013-07-14T18:26:06.207

Solve by recursion:

static IEnumerable<List<int>> GetCombinations(IEnumerable<List<int>> lists, IEnumerable<int> selected)
{
    if (lists.Any())
    {
        var remainingLists = lists.Skip(1);
        foreach (var item in lists.First().Where(x => !selected.Contains(x)))
            foreach (var combo in GetCombinations(remainingLists, selected.Concat(new int[] { item })))
                yield return combo;
    }
    else
    {
        yield return selected.ToList();
    }
}

static void Main(string[] args)
{
    List<List<int>> lists = new List<List<int>>
    {
        new List<int> { 1, 3, 6 },
        new List<int> { 1, 2, 6 },
        new List<int> { 1 },
        new List<int> { 2, 3 }
    };

    var combos = GetCombinations(lists, new List<int>()).Distinct();

    foreach (var combo in combos)
        Console.WriteLine("{ " + string.Join(", ", combo.Select(x => x.ToString())) + " }");

    return;
}

Output:

{ 3, 6, 1, 2 }
{ 6, 2, 1, 3 }

ytoledano · Accepted Answer · 2013-07-14T18:22:20.820

This solution is far from efficient:

    private static void Main()
    {
        List<List<int>> list = new List<List<int>>
            {
                new List<int>() {1, 3, 6}, //Booking 1
                new List<int>() {1, 2, 6}, //Booking 2
                new List<int>() {1}, //Booking 3
                new List<int>() {2, 3}
            };
        List<int[]> solutions = new List<int[]>();
        int[] solution = new int[list.Count];
        Solve(list, solutions, solution);
    }

    private static void Solve(List<List<int>> list, List<int[]> solutions, int[] solution)
    {
        if (solution.All(i => i != 0) && !solutions.Any(s => s.SequenceEqual(solution)))
            solutions.Add(solution);
        for (int i = 0; i < list.Count; i++)
        {
            if (solution[i] != 0)
                continue; // a caller up the hierarchy set this index to be a number
            for (int j = 0; j < list[i].Count; j++)
            {
                if (solution.Contains(list[i][j]))
                    continue;
                var solutionCopy = solution.ToArray();
                solutionCopy[i] = list[i][j];
                Solve(list, solutions, solutionCopy);
            }
        }
    }

It sounds like this can be solved more efficiently with Dynamic programming, but it's been a while since I took the relevant course.

Thank you very much ytoledano! It's not so many so performance is not an issue. — ekenman, Jul 14 '13 at 18:16

score 3 · Answer 3 · answered Jul 14 '13 at 19:07

A simple way to look at this problem would be to choose from all combinations of the list of values, where every value in the combination is unique.

First figure out what all the combinations of values are.

public static IEnumerable<IList<T>> Combinations<T>(IEnumerable<IList<T>> collections)
{
    if (collections.Count() == 1)
    {
        foreach (var item in collections.Single())
            yield return new List<T> { item };
    }
    else if (collections.Count() > 1)
    {
        foreach (var item in collections.First())
        foreach (var tail in Combinations(collections.Skip(1)))
            yield return new[] { item }.Concat(tail).ToList();
    }
}

Then you need a way to determine if all the values are unique. A simple way to figure that out would be to check if the count of distinct values equals the count of all values.

public static bool AllUnique<T>(IEnumerable<T> collection)
{
    return collection.Distinct().Count() == collection.Count();
}

Once you have all that, put it all together.

var collections = new[]
{
    new List<int> { 1, 3, 6 },
    new List<int> { 1, 2, 6 },
    new List<int> { 1 },
    new List<int> { 2, 3 },
};
var results =
    from combination in Combinations(collections)
    where AllUnique(combination)
    select combination;
// results:
//  3,6,1,2
//  6,2,1,3

How to get all combinations of several List

3 Answers3

Linked