How to combine lists with respect to precedence

Question

I have a List of strings like this :

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

And I have 4 lists to combine :

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

I want to make a new list from these 4 lists using ANDs and ORs from andOrList. Since AND has higher precedence than OR first I will apply ANDs so I will have these :

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

And finally combine these two templists because there is an OR :

var resulList = tempList1.Union(tempList2);

As you can see it's possible to do this by hand when there is defined number of lists and defined number of ANDs and ORs. But I couldn't figure out how to do it programmatically when there are n number of Lists to combine and n-1 number of ANDs and ORs. Can you help me with that? Thanks.

Answer 1

I suggest splitting execution into two stages:

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

E.g.

   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

in your case

  {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} 

Implementation

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

Test

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

Outcome

  29