Combination of List<List<int>>
Solution 1
It's quite similar to this answer I gave to another question:
var combinations = from a in A
from b in B
from c in C
orderby a, b, c
select new List<int> { a, b, c };
var x = combinations.ToList();
For a variable number of inputs, now with added generics:
var x = AllCombinationsOf(A, B, C);
public static List<List<T>> AllCombinationsOf<T>(params List<T>[] sets)
{
// need array bounds checking etc for production
var combinations = new List<List<T>>();
// prime the data
foreach (var value in sets[0])
combinations.Add(new List<T> { value });
foreach (var set in sets.Skip(1))
combinations = AddExtraSet(combinations, set);
return combinations;
}
private static List<List<T>> AddExtraSet<T>
(List<List<T>> combinations, List<T> set)
{
var newCombinations = from value in set
from combination in combinations
select new List<T>(combination) { value };
return newCombinations.ToList();
}
Solution 2
If the number of dimensions is fixed, this is simply SelectMany
:
var qry = from a in A
from b in B
from c in C
select new {A=a,B=b,C=c};
However, if the number of dimensions is controlled by the data, you need to use recursion:
static void Main() {
List<List<int>> outerList = new List<List<int>>
{ new List<int>(){1, 2, 3, 4, 5},
new List<int>(){0, 1},
new List<int>(){6,3},
new List<int>(){1,3,5}
};
int[] result = new int[outerList.Count];
Recurse(result, 0, outerList);
}
static void Recurse<TList>(int[] selected, int index,
IEnumerable<TList> remaining) where TList : IEnumerable<int> {
IEnumerable<int> nextList = remaining.FirstOrDefault();
if (nextList == null) {
StringBuilder sb = new StringBuilder();
foreach (int i in selected) {
sb.Append(i).Append(',');
}
if (sb.Length > 0) sb.Length--;
Console.WriteLine(sb);
} else {
foreach (int i in nextList) {
selected[index] = i;
Recurse(selected, index + 1, remaining.Skip(1));
}
}
}
Solution 3
How about following way of generating combinations using .Join method?
static void Main()
{
List<List<int>> collectionOfSeries = new List<List<int>>
{ new List<int>(){1, 2, 3, 4, 5},
new List<int>(){0, 1},
new List<int>(){6,3},
new List<int>(){1,3,5}
};
int[] result = new int[collectionOfSeries.Count];
List<List<int>> combinations = GenerateCombinations(collectionOfSeries);
Display(combinations);
}
This Method GenerateCombinations(..) does main work of generating combinations. This method is generic so could be used for generating combinations of any type.
private static List<List<T>> GenerateCombinations<T>(
List<List<T>> collectionOfSeries)
{
List<List<T>> generatedCombinations =
collectionOfSeries.Take(1)
.FirstOrDefault()
.Select(i => (new T[]{i}).ToList())
.ToList();
foreach (List<T> series in collectionOfSeries.Skip(1))
{
generatedCombinations =
generatedCombinations
.Join(series as List<T>,
combination => true,
i => true,
(combination, i) =>
{
List<T> nextLevelCombination =
new List<T>(combination);
nextLevelCombination.Add(i);
return nextLevelCombination;
}).ToList();
}
return generatedCombinations;
}
Display helper..
private static void Display<T>(List<List<T>> generatedCombinations)
{
int index = 0;
foreach (var generatedCombination in generatedCombinations)
{
Console.Write("{0}\t:", ++index);
foreach (var i in generatedCombination)
{
Console.Write("{0,3}", i);
}
Console.WriteLine();
}
Console.ReadKey();
}
Solution 4
//Done in 2 while loops. No recursion required
#include<stdio.h>
#define MAX 100
typedef struct list
{
int elements[MAX];
}list;
list n[10];
int number,count[10],temp[10];
void print();
int main()
{
int i,j,mult=1,mult_count;
printf("Enter the number of lists - ");
scanf("%d",&number);
for(i=0;i<number;i++)
{
printf("Enter the number of elements - ");
scanf("%d",&count[i]);
for(j=0;i<count[i];j++)
{
printf("Enter element %d - "j);
scanf("%d",&n[i].elements[j]);
}
}
for(i=0;i<number;i++)
temp[i]=0;
for(i=0;i<number;i++)
mult*=count[i];
printf("%d\n",mult);
mult_count=0;
while(1)
{
print();
mult_count++;
if(mult_count==mult)
break;
i=0;
while(1)
{
temp[i]++;
if(temp[i]==count[i])
{
temp[i]=0;
i++;
}
else break;
}
}
return 0;
}
void print()
{
int i;
for(i=0;i<number;i++)
{
printf("%d\n",n[i].elements[temp[i]]);
printf("\n");
}
}
Solution 5
Great solution from Abhijeet Nagre. Small improvement in case when some serie is empty or series are empty.
List<List<T>> generatedCombinations =
collectionOfSeries.Where(l => l.Any())
.Take(1)
.DefaultIfEmpty(new List<T>())
.First()
.Select(i => (new T[]{i}).ToList())
.ToList();
Related videos on Youtube
Giomuti
Updated on July 09, 2022Comments
-
Giomuti almost 2 years
I've a List of this type List> that contains this
List<int> A = new List<int> {1, 2, 3, 4, 5}; List<int> B = new List<int> {0, 1}; List<int> C = new List<int> {6}; List<int> X = new List<int> {....,....};
I want to have all combinations like this
1-0-6 1-1-6 2-0-6 2-1-6 3-0-6
and so on.
According to you is This possibile to resolve using Linq?
-
kaushikjain about 15 yearsIt's a cross product, trust Garry answer, it will do it.
-
-
Garry Shutler about 15 yearsHmmm, it's still possible based on my other references answer, you could just take a paramarray of sets and build it up. I'll ask for clarification in a comment.
-
Giomuti about 15 yearsYes guys the number of items is dynamic!
-
Marc Gravell about 15 yearsI see - you repeatedly cross 2 lists at a time in the loop - cute.
-
Giomuti about 15 yearsHow Can I modify the function "AllCombinationsOf" to pass all the list and only list<object>?
-
Garry Shutler about 15 yearsAllCombinationsOf will take any number of lists (due to the params) argument, so long as those lists contain the same type (in this case int). So you could call AllCombinationsOf(List<Car>, List<Car>, List<Car>, List<Car>) without changing any code.
-
Giomuti about 15 yearsI've tried, it functions. But I need to pass to the function the entire list not only single elements!
-
Giomuti about 15 yearsI've understood but i want to pass the entire List<List<Object>>
-
Garry Shutler about 15 yearsI don't understand. You want to pass it the list of combinations in order to create a list of combinations?
-
Giomuti about 15 yearsSorry for my english, I'm Italian. I' ve solved. This example maybe could help you! var A = new List<int>() { 1, 2, 3, 4, 5 }; var B = new List<int>() { 1, 3, 5 }; List<List<int>> L = new List<List<int>>(); L.Add(A); L.Add(B); var X = Combinations.AllCombinationsOf(L.ToArray()); Thanks very much.
-
Garry Shutler about 15 yearsIf that's how you need to use it you could change the method to this signature: AllCombinationsOf<T>(List<List<T>> sets) I think it would still work without any other changes to the code. Otherwise what you've done will work, yes.
-
Marc Gravell about 15 yearsThe biggest problem I can see with this approach is the number of allocations. With the array version, you don't have this - just the one array. It would be easy to pass in an Action<T[]> to enact on combinations...
-
Garry Shutler about 15 yearsIt is true, I was thinking about it last night. I'll have a think about it. However, it's currently readable (to me) and produces the correct result. So (potentially) obfusticating it in the name of performance may be a waste of time if it works sufficiently well.
-
Giomuti about 15 yearsHi, I need to verify, during combination, if a value is greater than other. What do I have to do? Thanks very much!!!
-
InsParbo over 6 yearsExcellent solution.