如何根据优先级组合列表

Question

我有一个这样的字符串列表：

List<string> andOrList = new List<string>();
andOrList.Add("AND");
andOrList.Add("OR");
andOrList.Add("AND");

我有 4 个列表要合并：

List<int> list1 = new List<int>(new int[] { 19, 23, 29 });
List<int> list2 = new List<int>(new int[] { 1, 4, 29 });
List<int> list3 = new List<int>(new int[] { 1, 5, 23 });
List<int> list4 = new List<int>(new int[] { 2, 4, 19 });

我想使用 andOrList 中的 AND 和 OR 从这 4 个列表中创建一个新列表。由于 AND 的优先级高于 OR 首先我将应用 AND，所以我将拥有这些：

   var tempList1 = list1.Intersect(list2).ToList();
   var tempList2 = list3.Intersect(list4).ToList();

最后合并这两个模板，因为有一个 OR ：

var resulList = tempList1.Union(tempList2);

如您所见，当列表数量和 AND 和 OR 数量已定义时，可以手动执行此操作。但是当有 n 个要组合的列表和 n-1 个 AND 和 OR 时，我无法弄清楚如何以编程方式执行此操作。你能帮我吗？谢谢

Answer 1

我建议将执行分成两个阶段：

1. Performs all `AND`s
2. Perform  all `OR`s

例如

   a & b & c | d | e & f & g | h  ==       // put the right order
  (a & b & c) | (d) | (e & f & g) | (h) == // perform ANDs
   a_b_c | d | e_f_g | h ==                // perform ORs
   final result

你的情况

  {19, 23, 29} & {1, 4, 29} | {1, 5, 23} & {2, 4, 19} ==     // put the right order
  ({19, 23, 29} & {1, 4, 29}) | ({1, 5, 23} & {2, 4, 19}) == // perform ANDs
  {29} | {} ==                                               // perform ORs
  {29}

实施

private static IEnumerable<T> CombinatorOrAnd<T>(IEnumerable<IEnumerable<T>> sources, 
                                                 IEnumerable<string> actions) {
  List<IEnumerable<T>> orList = new List<IEnumerable<T>>();

  // First, do all ANDs

  bool isFirst = true;
  IEnumerable<T> temp = null;

  using (var en = actions.GetEnumerator()) {
    foreach (var argument in sources) {
      if (isFirst) {
        temp = argument;
        isFirst = false;

        continue;
      }

      en.MoveNext();

      if (en.Current == "AND")
        temp = temp.Intersect(argument);
      else {
        orList.Add(temp);

        temp = argument;
      }
    }
  }

  orList.Add(temp);

  // Finally, perform all ORs 
  return orList.Aggregate((s, a) => s.Union(a));
}

测试

  List<int> list1 = new List<int>(new int[] { 19, 23, 29 });
  List<int> list2 = new List<int>(new int[] { 1, 4, 29 });
  List<int> list3 = new List<int>(new int[] { 1, 5, 23 });
  List<int> list4 = new List<int>(new int[] { 2, 4, 19 });

  List<string> andOrList = new List<string>();
  andOrList.Add("AND");
  andOrList.Add("OR");
  andOrList.Add("AND");

  var result = CombinatorOrAnd(new List<int>[] { list1, list2, list3, list4}, andOrList);

  Console.Write(string.Join(", ", result.OrderBy(item => item)));

结果

Answer 2

为迟来的回答道歉，但我在后台打开了这个。这个想法几乎是一样的：先做 ANDs，但是通过改变输入列表（的副本）来做到这一点。

public static IEnumerable<int> ProcessAndOr(List<string> andOrList, params List<int>[] Input)
{
    var lst = new List<IEnumerable<int>>(Input);
    for(int i = andOrList.Count -1  ; i >= 0 ; i--)
        if(andOrList[i] == "AND")
        {
            lst[i] = lst[i].Intersect(lst[++i]);
            lst.RemoveAt(i--);
        }
    return lst.SelectMany(l=>l).Distinct();
}

可以使用 var resultList = ProcessAndOr(andOrList, list1,list2,list3,list4); 调用示例并生成 29

PS，相反的顺序并不是真正必要的，但这样做是为了能够使用单个变量进行迭代。

如何根据优先级组合列表

How to combine lists with respect to precedence

c#

algorithm

list

operator-precedence