How to create a list of a list of integers based on a tree of Or and And objects?

user_1058292 0
Viewed 41

I want this result:

[[1,2],[1,3],[1,4,5,6],[1,4,5,7]]

from the following set of objects:

var andsOrs = 
  Ands(items: [
    single(1),
    Ors(items: [
      single(2),
      single(3),
      Ands(items: [
        single(4),
        single(5),
        Ors(items: [
          single(6),
          single(7),
        ]),
      ]),
    ]),
  ]);

I'm struggling to write a function that would produce the output, can anyone help? Any modern object oriented language would be fine really, c#, js, dart, c++.

dart recursion algorithm c#
1 Answers

If I understand correctly you are looking for functions named Ands, Ors and single that will give the desired result. The format of the desired result is a 2D array where the inner arrays list atomic values that are AND'ed, and the outer array lists items that are OR'ed.

Each of those functions should return that format, also single. So for instance, single(1) should return [[1]].

The Ors function should just concatenate the 2D items it gets as argument into a longer 2D array. So if for instance, Ors gets two items: [[1,2]] and [[3,4],[5,6]] then the return value should be [[1,2],[3,4],[5,6]].

The more complex one is Ands: it should perform a Cartesian product on the arguments it gets.

Here is an implementation in JavaScript. The notation of the input is a bit different, as items: as function argument would be invalid syntax. We can just pass each item as a separate argument and use spread syntax:

function single(i) {
    return [[i]];
}

function Ands(first, ...rest) {
    // Cartesian product, using recursion
    if (!rest.length) return first;
    let restResult = Ands(...rest);
    let result = [];
    for (let option of first) {
        for (let restOption of restResult) {
            result.push([...option, ...restOption]);
        }
    }
    return result;
}

function Ors(...items) {
    return items.flat(1); // Reduces 1 level of array depth (from 3 to 2)
    // Alternative syntax to get the same result:
    // return [].concat(...items)
}

var andsOrs = 
  Ands(
    single(1),
    Ors(
      single(2),
      single(3),
      Ands(
        single(4),
        single(5),
        Ors(
          single(6),
          single(7),
        ),
      ),
    ),
  );

console.log(andsOrs);

user_54598390
Related