Построение и фильтрация коллекции декартовых произведений (пользовательских объектов) с Linq - PullRequest
0 голосов
/ 17 апреля 2020

У меня есть список объектов:

public class Item
{
    public int Id { get; set; }
    public Slot Slot { get; set; }
    public List<string> Spells { get; set; }
}

Слот - это перечисление:

public enum Slot
{
    Necklace = 1,
    Ring = 2,
    Bracelet = 3
}

Конечный декартово произведение, которое я ищу, - это все возможные комбинации элементов, подходящих в в коллекцию объектов следующего типа:

public class Set
{
    public int Necklace { get; set; }
    public int LeftBrace { get; set; }
    public int RightBrace { get; set; }
    public int LeftRing { get; set; }
    public int RightRing { get; set; }
}
  • Каждый элемент может использоваться только один раз для набора.
  • Каждое свойство int в наборе ссылается на Item.Id
  • Элементы могут помещаться только в указанный слот и не могут быть добавлены в набор несколько раз.
  • Если набор содержит повторяющиеся заклинания для нескольких элементов, его не следует добавлять в декартово произведение или если это невозможно, отфильтровано из полученного перечисления.
  • Заклинания на предметах могут быть как минимум от одного до максимум четырех и никогда не дублируются на самом предмете.

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

var _neckItems = _filterList.Where(i => i.Slot.Contains(Slot.Necklace)).ToArray();
var _leftRingItems = _filterList.Where(i => i.Slot.Contains(Slot.Ring)).ToArray();
var _rightRingItems = _filterList.Where(i => i.Slot.Contains(Slot.Ring)).ToArray();
var _leftBraceItems = _filterList.Where(i => i.Slot.Contains(Slot.Bracelet)).ToArray();
var _rightBraceItems = _filterList.Where(i => i.Slot.Contains(Slot.Bracelet)).ToArray();

Вот как я настраиваю декартово произведение:

Item[][] items = {
    _neckItems,
    _leftRingItems,
    _rightRingItems,
    _leftBraceItems
};

var sets = CartesianHelper.CartesianProduct(items);

А вот и сам декартовый метод:

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 }));
}

Вот как я проецирую перечисление на наборы:

var projectedSets = from s in sets.GroupBy(s => s.SelectMany(ss => ss.Spells).Distinct()).Select(x => x.First())
    where s.ToArray()[1].Id != s.ToArray()[2].Id
    && s.ToArray()[3].Id != s.ToArray()[4].Id
    select new Set
    {
        Necklace = s.ToArray()[0].Id,
        LeftRing = s.ToArray()[1].Id,
        RightRing = s.ToArray()[2].Id,
        LeftBrace = s.ToArray()[3].Id,
        RightBrace = s.ToArray()[4].Id,
    };

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

Что-то не так с моей группой запросов linq, поскольку она не отфильтровывает повторяющиеся заклинания в наборах и возможно, лучше всего перед тем, как перейти к этой точке, модифицировать декартовой метод.

Последнее условие, которое я хотел бы иметь, - возможность рассматривать пустые слоты в любом данном наборе. Конечной целью является определение максимального количества покрываемых слотов с учетом заданного списка предметов. Также следует отметить, что в окончательном решении перечисленные мной слоты на самом деле составляют только 3 из 15.

edit - я должен уточнить, что конечным результатом является максимальное количество покрытых слотов И максимальное количество заданных уникальных заклинаний набор предметов.

Спасибо за понимание и помощь в этом!

1 Ответ

0 голосов
/ 18 апреля 2020

Ниже приведены шаги, которые я выполняю, чтобы выполнить декартово произведение произвольного числа массивов целых чисел.

Скажем, у нас есть пять массивов ниже:

  var items1 = new int[]{1, 2, 3, 4};
  var items2 = new int[]{5, 6, 7, 8};
  var items3 = new int[]{9, 10, 11, 12};
  var items4 = new int[]{13, 14, 15, 16};
  var items5 = new int[]{17, 18, 19, 20};

И давайте скажем, у нас есть класс Set, который будет содержать элемент декартового произведения:

// I named the property like this to allow further manipulation afterward
class Set
{
  public int Item_1 { get; set; }
  public int Item_2 { get; set; } 
  public int Item_3 { get; set; }
  public int Item_4 { get; set; }
  public int Item_5 { get; set; }
}

Таким образом, добавление массива потребует от нас добавить еще одно свойство в класс Set. Предполагая, что это не страшно, давайте перейдем к следующему шагу.

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

Метод 1: использование Выражение запроса Linq

 var cp1 = 
    from i1 in items1
    from i2 in items2
    from i3 in items3
    from i4 in items4
    from i5 in items5
    select new Set
    {
      Item_1 = i1,
      Item_2 = i2,
      Item_3 = i3,
      Item_4 = i4,
      Item_5 = i5
    };

В большинстве случаев этого достаточно для выполнения декартового произведения, но добавление другой операции в операцию потребует изменения запроса. Итак, допустим, у нас есть требование создать декартово запрос продукта, который будет работать для любого количества коллекций, которые мы передаем ему. Перед реализацией этого метода, давайте посмотрим, как мы можем выполнить вышеупомянутый запрос, используя лямбда-выражения:

Метод 2: вручную, но используя лямбда-выражения

 var cp2 = items1.SelectMany(
    i1 => items2.SelectMany(
    i2 => items3.SelectMany(
    i3 => items4.SelectMany(
    i4 => items5.Select(
    i5 => new Set
    {
      Item_1 = i1,
      Item_2 = i2,
      Item_3 = i3,
      Item_4 = i4,
      Item_5 = i5
    })))));

Еще раз, это работает, но добавление еще одной коллекции к операции потребует изменения запроса. Но что интересно в этом, так это то, как мы рекурсивно связываем метод SelectMany. Поскольку в основном Linq работает с деревьями выражений, мы можем динамически построить дерево выражений предыдущего запроса, чтобы реализовать декартово произведение произвольного числа массивов:

Метод 3: Динамическое построение дерева выражений

MethodCallExpression CartesianProductExpression(int[][] items)
{
  var pes = new List<ParameterExpression>();
  return BuildExpression(items, pes, items.Length);
}

MethodCallExpression BuildExpression(int[][] items, List<ParameterExpression> pes, int numberOfArray)
{
  var queryable = items[0].AsQueryable<int>();
  ParameterExpression pe = Expression.Parameter(typeof(int), $"i{pes.Count+1}");
  pes.Add(pe);

  if(pes.Count == numberOfArray)
  {
    NewExpression newTripleExpression = Expression.New(typeof(Set));
    MemberBinding[] bindings = new MemberBinding[pes.Count];
    var index = 0;
    foreach(var p in pes)
    {
      bindings[index++] = SetBindings.GetBinding($"Item_{index}", p);
    }
    Expression selectBody = Expression.MemberInit(newTripleExpression, bindings);
    return Expression.Call(
      typeof(Queryable),
      "Select",
      new Type[] { queryable.ElementType, typeof(Set) },
      queryable.Expression,
      Expression.Lambda<Func<int, Set>>(selectBody, new ParameterExpression[] { pe }));
  }

  return Expression.Call(
      typeof(Queryable),
      "SelectMany",
      new Type[] { queryable.ElementType, typeof(Set) },
      queryable.Expression,
      Expression.Lambda<Func<int, IEnumerable<Set>>>(BuildExpression(items.Skip(1).ToArray(), pes, numberOfArray), new ParameterExpression[] { pe }));
}

// ... In another class file
static class SetBindings
{
  public static MemberBinding GetBinding(string propertyName, ParameterExpression pe)
  {
    MemberInfo member = typeof(Set).GetMember(propertyName)[0];
    return Expression.Bind(member, pe);
  }
}

Этот метод можно использовать следующим образом:

int[][] items = new int[][] {items1, items2, items3, items4, items5};
var queryable = items[0].AsQueryable<int>();
var expression = CartesianProductExpression(items);
IQueryable<Set> cp3 = queryable.Provider.CreateQuery<Set>(expression);

В этом методе добавление другого массива будет включать только добавление другого свойства в класс Set.

Вот так выглядит результат в Linqpad: enter image description here

Итак, вернемся к вашему вопросу, вы можете интерполировать это решение в вашем случае использования. Например, вместо:

var _neckItems = _filterList.Where(i => i.Slot == Slot.Necklace).ToArray();
\\...

Вы можете напрямую проецировать на Id следующим образом:

var _neckItems = _filterList.Where(i => i.Slot == Slot.Necklace).Select(i => i.Id).ToArray()
//...

Затем используйте один из вышеуказанных методов.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...