How to get all combinations of several List <int>

Question

It differs from the solution considered above in that the list item can appear only once for each line.

This is for the reservation system for my resort. Different employees can perform different procedures.

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

Each list (reservation) contains a number of such numbers (these are those who can make a reservation):

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

I would like to see all possible combinations where a number can appear in only one place. There are two possibilities in the above list:

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

This is for the first combination:

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

I hope this question becomes a little clearer.

Answer 1

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 seems that this can be solved more efficiently with the help of dynamic programming, but some time has passed since I took the appropriate course.

Answer 2

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 } 

Answer 3

An easy way to address this problem is to choose from all combinations of a list of values ​​where each value in the combination is unique.

First find out what all 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 to determine if all values ​​are unique. An easy way to understand this would be to check if the counting of different values ​​is equal to the number of all values.

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

Once you have it all, 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