Я считаю, что вы ищете декартово произведение каждого элемента набора мощности"набора префиксов" вашего набора последовательностей.Давайте разберем это:
Во-первых, у вас есть набор входных последовательностей:
IEnumerable<IEnumerable<int>> inputSet = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};
«Набор префиксов» inputSet:
{{}, {1,2,3}, {{1,2,3}, {4,5}}, {{1,2,3}, {4,5}, {6,7,8}}}
Декартово произведение набора последовательностей дает все комбинации по 1 элементу из каждой последовательности.
Я думаю, что вы ищете: (псевдокод)
foreach (element in the above prefix set)
{
Print(cartesian product of the sequences in this element);
}
Следующееявляются методами расширения, которые я использую для создания декартовых произведений, наборов мощности и т. д.: * 10101 *
public static class CombinatorialExtensionMethods {
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}));
}
public static IEnumerable<IEnumerable<T>> CartesianPower<T>(this IEnumerable<T> sequence, int power)
{
var sequences = Enumerable.Repeat<IEnumerable<T>>(sequence,power);
return sequences.CartesianProduct<T>();
}
public static IEnumerable<IEnumerable<T>> Permute<T>(this IEnumerable<T> seq, int k)
{
var sequences = Enumerable.Repeat<IEnumerable<T>>(seq,k);
IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
where !accseq.Contains(item)
select accseq.Concat(new[] {item}));
}
public static IEnumerable<IEnumerable<int>> Choose(this IEnumerable<int> seq, int k)
{
var sequences = Enumerable.Repeat<IEnumerable<int>>(seq,k);
IEnumerable<IEnumerable<int>> emptyProduct = new[] { Enumerable.Empty<int>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
where accseq.All(accitem => accitem.CompareTo(item) < 0)
select accseq.Concat(new[] {item}));
}
public static IEnumerable<IEnumerable<T>> Choose<T>(this IEnumerable<T> seq, int k)
{
IEnumerable<int> idxSequence = Enumerable.Range(0, seq.Count());
IEnumerable<IEnumerable<int>> idxChoose = idxSequence.Choose(k);
IEnumerable<IEnumerable<T>> result = Enumerable.Empty<IEnumerable<T>>();
foreach (IEnumerable<int> permutation in idxChoose)
{
IEnumerable<T> item = Enumerable.Empty<T>();
foreach (int index in permutation)
{
item = item.Concat(new[] { seq.ElementAt(index) });
}
result = result.Concat(new[] { item });
}
return result;
}
public static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> seq)
{
IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };
for (int i=1; i<=seq.Count(); i++)
{
result = result.Concat(seq.Choose<T>(i));
}
return result;
}
}
Используя их, код для вашего примера будет выглядеть так:
IEnumerable<IEnumerable<int>> sequences = new[] {new[] {1,2,3}, new[] {4,5}, new[] {6,7,8}};
IEnumerable<IEnumerable<IEnumerable<int>>> prefixSet = new[] {new[] { Enumerable.Empty<int>() }};
for (int i=0; i<sequences.Count(); i++)
{
IEnumerable<IEnumerable<int>> prefixSequence = Enumerable.Empty<IEnumerable<int>>();
for (int j=0; j<=i; j++)
{
prefixSequence = prefixSequence.Concat(new[] { sequences.ElementAt(j) });
}
prefixSet = prefixSet.Concat(new[] { prefixSequence });
}
foreach (IEnumerable<IEnumerable<int>> item in prefixSet)
{
Console.WriteLine(item.CartesianProduct<int>());
}