Динамическое декартово произведение

демонстрация класса:

class item
{
    public string name { get; set; }
    public int level { get; set; }
}

демонстрация данных:

List<item> all = new List<item>();
all.Add(new item { name = "Red", level = 0 });
all.Add(new item { name = "Blue", level = 0 });

all.Add(new item { name = "S", level = 1 });
all.Add(new item { name = "M", level = 1 });
all.Add(new item { name = "L", level = 1 });

all.Add(new item { name = "Man", level = 2 });
all.Add(new item { name = "Woman", level = 2 });

Мне нужно сгруппировать по уровню и объединить все имя , это Декартово произведение вопрос. Результат такой:

Красный - S - Мужчина
Красный - S - Женщина
Красный - M - Мужчина
Красный - M - Женщина
Красный - L - Мужчина
Красный - L - Женщина
Синий - S - Мужчина
Синий - S - Женщина
Синий - M - Мужчина
Синий - M - Женщина
Синий - L - Мужчина
Синий - L - Женщина

Если уровень был исправлен, решение с кодом ниже:

foreach(var _0 in all.Where(m => m.level == 0))
{
    foreach(var _1 in all.Where(m => m.level == 1))
    {
        foreach(var _2 in all.Where(m => m.level == 2))
        {
            Console.WriteLine(_0.name + "-" + _1.name + "-" + _2.name);
        }
    }
}

Но большой вопрос: уровень динамический, я просто кодирую так:

for(int i = 0; i < level; i++)
{
    //some code ...
}

Поскольку мой настоящий проект - это Javascript, поэтому, пожалуйста, дайте мне простой код (не linq). Большое спасибо за помощь.


c# cartesian
person jian.wu    schedule 22.08.2016    source источник
comment
Пожалуйста, пометьте свои вопросы языком, не включайте его в заголовок.   -  person Jonathon Reinhart    schedule 22.08.2016

Ответы (2)


arrow_upward
0
arrow_downward

Я бы начал с создания списка, содержащего элементы для каждого уровня:

var levels = new List<List<item>>();
foreach (var item in all)
{
    while (levels.Count <= item.level)
        levels.Add(new List<item>());
    levels[item.level].Add(item);
}

а затем заполните результат, используя простой рекурсивный метод:

var result = new List<string>();
AddCombinations(result, levels, 0, null);

где метод:

static void AddCombinations(List<string> result, List<List<item>> levels, int level, string path)
{
    if (level >= levels.Count)
    {
        result.Add(path);
        return;
    }
    foreach (var item in levels[level])
        AddCombinations(result, levels, level + 1, path == null ? item.name : path + " - " + item.name);
}

Вместо рекурсии я мог бы настроить реализацию из моего ответа на Каждая комбинация 1 элемента из каждой из N коллекций для итеративного построения результата на месте, если хотите, но я думаю, что вышеизложенного должно быть достаточно.

person Ivan Stoev    schedule 22.08.2016

arrow_upward
0
arrow_downward

Что-то вроде этого должно работать:

var lines = CartesianProduct(all, 0);
foreach(var line in lines) {
   Console.WriteLine(line);
}

List<string> CartesianProduct(List<item> items, int level) {
   List<string> result = new List<string>();
   List<string> itemsOnThisLevel = new List<string>();
   foreach(var it in items) {
      if (it.level == level) itemsOnThisLevel.Add(it.name);
   }
   if (!itemsOnThisLevel.Any()) {
      result.Add("");
      return result;
   }
   var itemsOnLowerLevels = CartesianProduct(items, level+1);
   foreach(var it in itemsOnThisLevel) {
      foreach(var it2 in itemsOnLowerLevels) {
         result.Add(it2 + " - " + it);
      } 
   }
   return result
}

РЕДАКТИРОВАТЬ: удалены выражения linq по запросу автора.

person suwik    schedule 22.08.2016