Всем привет!
Есть такая задача:
на входе несколько массивов переменной длины
значения всех элементов массивов уникальны на уровне всего входного множества
на выходе должен быть список массивов со всеми возможными уникальными сочетаниями (элементы сочетания из массивов должны следовать порядку массивов)
object[N][] input = new []
{
new object[n1];
new object[n2];
new object[n3];
...
new object[nN]; (всего N массивов)
}
комбинируем, должны получить
List<object[N]>
мне реализация видится примерно так:
1) комбинируем первые два массива
2) полученный скомбинированный набор комбинируем со следующим
3) повторяем 2) пока массивы не кончатся
Может кто-нибудь подскажет алгоритм получше?
Или вообще готовый вариант
Спасибо...
PS. размерность и количество массивов очень невелики (примерно <5), так что производительностью можно не заморачиваться
D>Может кто-нибудь подскажет алгоритм получше?
По описанию вроде как самая простая рекурсия
Если гарантировано что input.Length != 0 и input[depth].Length != 0 — то что-то такое:
static void seqList(object[][] input, int depth, object[] current, List<object[]> result)
{
if(depth < input.Length - 1)
{
foreach(var oi in input[depth])
{
current[depth] = oi;
seqList(input, depth+1, current, result);
}
} else
{
foreach(var oi in input[depth])
{
current[depth] = oi;
result.Add((object[])current.Clone());
}
}
}
//вызов:
var result = new List<object[]>(input.Aggregate(1, (x,y) => x * Math.Max(1, y.Length)));
seqList(input, 0, new object[input.Length], result);
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть такая задача:
D>на входе несколько массивов переменной длины
D>значения всех элементов массивов уникальны на уровне всего входного множества
D>на выходе должен быть список массивов со всеми возможными уникальными сочетаниями (элементы сочетания из массивов должны следовать порядку массивов)
Это называется
Cartesian product
Пример реализации:
https://stackoverflow.com/questions/4423838/cartesian-product-n-x-m-dynamic-array
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть такая задача:
D>на входе несколько массивов переменной длины
D>значения всех элементов массивов уникальны на уровне всего входного множества
D>на выходе должен быть список массивов со всеми возможными уникальными сочетаниями (элементы сочетания из массивов должны следовать порядку массивов)
D>D>object[N][] input = new []
D>{
D> new object[n1];
D> new object[n2];
D> new object[n3];
D> ...
D> new object[nN]; (всего N массивов)
D>}
D>
D>комбинируем, должны получить
D>D>List<object[N]>
D>
D>мне реализация видится примерно так:
D>1) комбинируем первые два массива
D>2) полученный скомбинированный набор комбинируем со следующим
D>3) повторяем 2) пока массивы не кончатся
D>Может кто-нибудь подскажет алгоритм получше?
Самый очевидный вариант — это понять, что вы используете систему счисления с неравномерным основанием.
IEnumerable<object[]> CartesianProduct(object[][] input)
{
var N = input.Count;
var number = new int[N];
do
{
yield return GetPermutation(input, number);
Increment(input, number);
} while(!IsZero(number);
}
static object[] GetPermutation(object[][] input, int[] number)
{
var permutation = new object[number.Count];
for(int i=0;i<number.Count;i++)
{
permutation[i] = input[i][number[i]];
}
}
static void Increment(object[][] input, int[] number)
{
for(int i=0; i<number.Count; i++)
{
number[i]++;
if(number[i] = input[i].Count)
number[i]=0;
else break;
}
}
static bool IsZero(int[] number) => number.All(p=>p==0);
D>Или вообще готовый вариант
Здравствуйте, Буравчик, Вы писали:
Б>Пример реализации:
Б>https://stackoverflow.com/questions/4423838/cartesian-product-n-x-m-dynamic-array
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}));
}
That would let you write code like this:
int[][] items = {
new[] { 11001, 54010, 60621 },
new[] { 11001, 60621 },
new[] { 60621 }
};
var routes = CartesianProduct(items);
foreach (var route in routes)
Console.WriteLine(string.Join(", ", route));
And get output like this:
11001, 11001, 60621
11001, 60621, 60621
54010, 11001, 60621
54010, 60621, 60621
60621, 11001, 60621
60621, 60621, 60621
