Нахождение оптимальных узлов, наличие которых удовлетворяет вложенной логике JSON

Question

Ниже JSON, который я использую для создания следующего пользовательского интерфейса:

{
    "Text" : "1. Parent group"
    "Logic" : "all of the following",
    "Id":"1" //some unique id
    "children": [
        {
            "Text' : "1.1 Level Child group"
            "Logic' : "1 or more of the following",
            "Id':"1.1" //some unique id,
            "children" :  [
                {
                    "Text' : "1.1.1 Level Child group"
                    "Logic' : "all of the following",
                    "Id':"1.1.1" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.1.1 Level Child"
                            "Id':"1.1.1.1" //some unique id,

                        },
                        {
                            "Text' : "1.1.1.2 Level Child"
                            "Id':"1.1.1.2" //some unique id,
                            "Logic" : "one or more of the following",
                            "children" : [
                                      { 
                                      "Text": "1.1.1.2.1 Level Child", 
                                      "Id": "1.1.1.2.1" 
                                      }, 
                                      { 
                                     "Text": "1.1.1.2.2 Level Child", 
                                      "Id": "1.1.1.2.2" 
                                      }, 
                              ]
                        }
                    ]
                },
                {
                    "Text' : "1.1.2 Level Child group"
                    "Id':"1.1.2" //some unique id,
                },
                {
                    "Text' : "1.1.3 Level Child group"
                    "Id':"1.1.3" //some unique id,
                },
                {
                    "Text' : "1.1.4 Level Child group"
                    "Logic' : "one or more of the following",
                    "Id':"1.1.4" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.4.1 Level Child"
                            "Id':"1.1.4.1" //some unique id,
                        },
                        {
                            "Text' : "1.1.4.2 Level Child"
                            "Id':"1.1.4.2" //some unique id,
                        }
                    ]
                },
                {
                    "Text' : "1.1.5 Level Child group"
                    "Logic' : "all of the following",
                    "Id':"1.1.5" //some unique id,
                    "children": [
                        {
                            "Text' : "1.1.5.1 Level Child"
                            "Id':"1.1.5.1" //some unique id,
                        },
                        {
                            "Text' : "1.1.5.2 Level Child"
                            "Id':"1.1.5.2" //some unique id,
                        }
                    ]
                }

            ]
        },
        {
            "Text" : "1.2 Level Child"
            "Id":"1.2" //some unique id
        }
    ]
}

 1. Parent group (all of the following)

    1.1 Level Child group (1 or more )

        1.1.1 Level Child group (all of the following)
            1.1.1.1 Level Child // selectable
            1.1.1.2 Level Child // selectable

        1.1.2 Level Child   // selectable

        1.1.3 Level Child  // selectable

        1.1.4 Level Child group (one or more of the following)
            1.1.4.1 Level Child  // selectable
            1.1.4.2 Level Child  // selectable

        1.1.5 Level Child group (all of the following)
            1.1.5.1 Level Child  // selectable
            1.1.5.2 Level Child  // selectable

    1.2 Level Child   // selectable

Узел рабочих логи c:

1. только узлы без дочерних элементов могут быть выбраны пользователем.

2. Узел выбирается неявно, если Logi c является «всем следующим», если и только если выбраны все его вложенные дочерние элементы

3. Узел выбирается неявно, если logi c равен «n или более из следующих», если только если выбраны его «n» вложенные потомки

Сценарий: если пользователь выбирает 1.1.2 (он неявно удовлетворяет 1.1 ) и 1.2 , тогда "1. родительская группа" равна "Met" , поэтому он выбран (делает всю группу встреченной);

Сценарий: если пользователь выбирает 1.1.1.1 , пользователь должен выбрать 1.1.1.2 , поэтому что 1.1.1 соответствует "Мет" и выбор 1.2 сделает всю группу "Мет".

Фактическая необходимость заключается в поиске оптимального идентификаторы, когда "родительская группа не м et ":

Если при выборе каких-либо узлов и самой верхней родительской группы 1045 * все еще не" выполнено ". Затем, нажав кнопку, мне нужно найти и вернуть оптимальные идентификаторы узлов, присутствие которых сделало бы «родительскую группу» «Меткой».

ПРИМЕЧАНИЕ: при поиске оптимального Идентификаторы узла должны иметь значение для дочерних групп, если выбран любой из его дочерних элементов.

Например, например:

Если только 1.2 выбрано Пользователь, самый быстрый способ сделать так, чтобы «родительская группа» встретилась, это выбрать 1.1.2 . Но если в 1.1.1 выбраны какие-либо дочерние элементы, то я должен отдать приоритет узлу 1.1.1 , в результате мне нужно вернуть следующие идентификаторы: [ 1.1.1.2, 1.1.1, 1.1 ]

Не уверен, какой тип алгоритма мне следует использовать для решения этой проблемы.

Answer 1

Здесь краткий подход с рассмотрением ограничений, которые теперь находятся в наборе данных, обозначенном q: 'some' или q: 'every'.

function select(node, selected) {

    function iter(node) {
        if (!node.children) return [node.Id];
		
        var temp = node.children.map(iter);

        if (node.q === 'every') return [...temp.flat(), node.Id];

        var filtered = temp.filter(a => a.some(v => selected.includes(v)));
        if (filtered.length) return [...filtered.flat(), node.Id];

        return [...temp.reduce((a, b) => b.length < a.length ? b : a), node.Id];
    }

    return iter(node).filter(v => !selected.includes(v));
}

var data = { q: 'every', Text: "1. Parent group", Logic: "all of the following", Id: "1", children: [{ q: 'some', Text: "1.1 Level Child group", Logic: "1 or more of the following", Id: "1.1", children: [{ q: 'every', Text: "1.1.1 Level Child group", Logic: "all of the following", Id: "1.1.1", children: [{ Text: "1.1.1.1 Level Child", Id: "1.1.1.1" }, { Text: "1.1.1.2 Level Child", Id: "1.1.1.2" }] }, { Text: "1.1.2 Level Child group", Id: "1.1.2" }, { Text: "1.1.3 Level Child group", Id: "1.1.3" }, { q: 'some', Text: "1.1.4 Level Child group", Logic: "one or more of the following", Id: "1.1.4", children: [{ Text: "1.1.4.1 Level Child", Id: "1.1.4.1" }, { Text: "1.1.4.2 Level Child", Id: "1.1.4.2" }] }, { q: 'every', Text: "1.1.5 Level Child group", Logic: "all of the following", Id: "1.1.5", children: [{ Text: "1.1.5.1 Level Child", Id: "1.1.5.1" }, { Text: "1.1.5.2 Level Child", Id: "1.1.5.1" }] }] }, { Text: "1.2 Level Child", Id: "1.2" }] };

console.log(select(data, ["1.2"]));
console.log(select(data, ["1.2", "1.1.1.1"]));
console.log(select(data, ["1.1.1.1"]));

.as-console-wrapper { max-height: 100% !important; top: 0; }