javascript - 树递归与笛卡尔实现

Question

我需要帮助从一棵树中找到所有组合的可能性

我阅读了很多关于笛卡尔积的文档，尝试了很多东西，但似乎没有一个能正常工作......

这是我的树

var data = [
  {
    "id": 5,
    "name": "Support papier",
    "type": "filter",
    "children": [
      {
        "id": 24,
        "name": "60 g/m² papier mat",
        "type": "value",
        "children": []
      },
      {
        "id": 7,
        "name": "90 g/m² papier couché",
        "type": "value",
        "children": [
          {
            "id": 8,
            "name": "Propriété papier",
            "type": "filter",
            "children": [
              {
                "id": 18,
                "name": "Papier mat",
                "type": "value",
                "children": [],
              },
              {
                "id": 60,
                "name": "Papier brillant",
                "type": "value",
                "children": [],
              }
            ]
          }
        ],
      }
    ]
  }
]

这是我的预期结果:

[
  [
    {id: 5, name:"support papier", type: "filter"}, 
    {id: 24, name:"60 g/m² papier mat", type: "value"},

  ],
  [
    {id: 5, name:"support papier", type: "filter"}, 
    {id: 7, name:"90 g/m² papier mat", type: "value"},
    {id: 8, name:"Propriété papier", type: "filter"}, 
    {id: 18, name:"Papier mat", type: "value"},
  ],
  [
    {id: 5, name:"support papier", type: "filter"}, 
    {id: 7, name:"90 g/m² papier mat", type: "value"},
    {id: 8, name:"Propriété papier", type: "filter"}, 
    {id: 60, name:"Papier brillant", type: "value"},
  ]
]

当然，每个空数组都可以填充... :)

谢谢你的帮助:)

Answer 1

您可以获取每个级别并将下一个较低级别映射到结果集。

Now, what is it doing?

The first part of collecting data is just getting all nodes to the end of the children's objects.

The other part is using a cartesian product for children which object has

type === 'value'

This works in two steps

1. Collect all items by getting the data and map these items with the actual object.

2. Create a cartesian product from an array of items.

The rest is just either pushing a new array with parts and adding the actual object (without children) or if no children are available, only the actual object in an array.

function getData(array) {
    return array.reduce((r, { children, ...o }) => {
        if (children.length) {
            var parts = o.type === 'value'
                    ? children
                        .map(({ children = [], ...p }) => getData(children).map(q => [p, ...q]))
                        .reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []))
                    : getData(children);

            r.push(...parts.map(q => [o, ...q]));
        } else {
            r.push([o]);
        }
        return r;
    }, []);
}

var data = [{ id: 5, name: "Support papier", type: "filter", children: [{ id: 24, name: "60 g/m² papier mat", type: "value", children: [{ id: 9, name: "Finition", type: "filter", children: [{ id: 19, name: "Sans finition", type: "value", children: [] }, { id: 20, name: "Vernis anti UV", type: "value", children: [] }] }, { id: 8, name: "Propriété papier", type: "filter", children: [{ id: 60, name: "Papier brillant", type: "value", children: [] }, { id: 18, name: "Papier mat", type: "value", children: [] }] }] }, { id: 7, name: "90 g/m² papier couché", type: "value", children: [{ id: 8, name: "Propriété papier", type: "filter", children: [{ id: 18, name: "Papier mat", type: "value", children: [] }, { id: 60, name: "Papier brillant", type: "value", children: [] }] }] }] }],
    result = getData(data);

console.log(result);

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