需要创建一个JS嵌套字典的所有keypath的数组

问题描述 投票：0回答：1

我以这本词典为例；这是来自World Lexicon of Grammaticalization（WLG）的信息，我已将其重新打包到嵌套字典中。这个特定的字典对“do”可以语法化的所有内容（？）进行编码，这在 WLG 中得到了证明：

let tDict = {
    "Causative": {},
    "Emphasis": {},
    "D-Necessity": {
        "Future": {
            "E-Necessity": {}
        },
        "B-Necessity": {
            "Future": {
                "E-Necessity": {}
            },
            "Purpose": {
                "Cause": {
                    "Adversative": {
                        "Mirative": {}
                    }
                },
                "Infinitive": {}
            }
        },
        "E-Necessity": {},
        "D-Possibility": {
            "D-Necessity": {}
        },
        "Purpose": {
            "Cause": {
                "Adversative": {
                    "Mirative": {}
                }
            },
            "Infinitive": {}
        }
    },
    "Pro-Verb": {},
    "Progressive": {
        "Habitual": {},
        "Imperfective": {},
        "Present": {}
    }
};

我想要的是一些接受 

tDict
并输出所有最大深度关键路径的列表的函数，即预期输出是：

[
    ["Causative"],
    ["Emphasis"],
    ["D-Necessity", "Future", "E-Necessity"],
    ["D-Necessity", "B-Necessity", "Future", "E-Necessity"],
    ["D-Necessity", "B-Necessity", "Purpose", "Cause", "Adversative", "Mirative"],
    ["D-Necessity", "B-Necessity", "Purpose", "Infinitive"],
    ["D-Necessity", "E-Necessity"],
    ["D-Necessity", "D-Possibility", "D-Necessity"],
    ["D-Necessity", "Purpose", "Cause", "Adversative", "Mirative"],
    ["D-Necessity", "Purpose", "Infinitive"],
    ["Pro-Verb"],
    ["Progressive", "Habitual"],
    ["Progressive", "Imperfective"],
    ["Progressive", "Present"]
]

我已经有一个函数可以计算两个数组的笛卡尔积。可以使用单元素数组作为第一个参数重复调用它，这样效果只是将第一个参数同时连接到第二个参数的每个子数组上：

var Cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []);

tCart1 = Cartesian(["w"], ["x","y","z"]);
console.log("1st Cartesian Product:");
console.log(tCart1);

tCart2 = Cartesian(["v"], tCart1);
console.log("2nd Cartesian Product:");
console.log(tCart2);

tCart3 = Cartesian(["u"], tCart2);
console.log("3rd Cartesian Product:");
console.log(tCart3);

所以我的想法是创建一个递归函数，利用 

Cartesian
的属性，通过使用它将每个字典键连接到较低级别调用的每个子数组的前面：

function GetAllKeypaths(t) {
    return Object.keys(t).map( e => Cartesian([e], GetAllKeypaths(t[e]) ) );
}

这……行不通。它在各处创建了各种重复的字典键，并添加了许多额外的不必要的嵌套。

我确实想到，也许嵌套问题是因为 

Cartesian
返回一个嵌套数组，它只是被平滑到最终输出数组的单个索引中，因为 
Array.map
进行了 1 对 1 映射。所以我尝试将所有 
Cartesian
输出分别转储到一个公共表中：

function GetAllKeypaths(t) {
    let tOut = [];
    Object.keys(t).forEach( e => { 
        Cartesian([e], GetAllKeypaths(t[e])).forEach( e2 => { tOut.push(e2) });
    });
    return tOut;
}

但这也不起作用 - 它返回一个完全空的数组。

我应该怎么做才能返回所需的输出？

let tDict = {
    "Causative": {},
    "Emphasis": {},
    "D-Necessity": {
        "Future": {
            "E-Necessity": {}
        },
        "B-Necessity": {
            "Future": {
                "E-Necessity": {}
            },
            "Purpose": {
                "Cause": {
                    "Adversative": {
                        "Mirative": {}
                    }
                },
                "Infinitive": {}
            }
        },
        "E-Necessity": {},
        "D-Possibility": {
            "D-Necessity": {}
        },
        "Purpose": {
            "Cause": {
                "Adversative": {
                    "Mirative": {}
                }
            },
            "Infinitive": {}
        }
    },
    "Pro-Verb": {},
    "Progressive": {
        "Habitual": {},
        "Imperfective": {},
        "Present": {}
    }
};

var Cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []);

function GetAllKeypaths(t) {
    return Object.keys(t).map( e => Cartesian([e], GetAllKeypaths(t[e]) ) );
}

console.log(GetAllKeypaths(tDict));

GetAllKeypaths = function (t) {
    let tOut = [];
    Object.keys(t).forEach( e => { 
        Cartesian([e], GetAllKeypaths(t[e])).forEach( e2 => { tOut.push(e2) });
    });
    return tOut;
}

console.log(GetAllKeypaths(tDict));

javascript arrays dictionary key
1个回答
0
投票

看看您使用 

.forEach()
的方法，您正在尝试使用可能为空的数组来获取密钥的笛卡尔积。如果您考虑一个简单的对象，例如 
{a: {}}
，您会尝试在键上的循环中执行 
cartesian(['a'], [])
，这将为您提供一个空数组。此问题会向上传播到递归调用，导致返回值为空数组。一种选择是检查递归调用的长度是否为空，如果是，则返回当前密钥（这是基本情况），否则执行递归调用。在下面的代码中，我基本上已经做到了这一点，但是，在我们要递归的对象上使用 
Object.keys()
来确定递归调用是否将返回一个空数组（我们可以这样做，因为空对象的关键路径将是一个空数组）。

let tDict = { "Causative": {}, "Emphasis": {}, "D-Necessity": { "Future": { "E-Necessity": {} }, "B-Necessity": { "Future": { "E-Necessity": {} }, "Purpose": { "Cause": { "Adversative": { "Mirative": {} } }, "Infinitive": {} } }, "E-Necessity": {}, "D-Possibility": { "D-Necessity": {} }, "Purpose": { "Cause": { "Adversative": { "Mirative": {} } }, "Infinitive": {} } }, "Pro-Verb": {}, "Progressive": { "Habitual": {}, "Imperfective": {}, "Present": {} } };

const cartesian = (a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []);

function getAllKeyPaths(t) {
  return Object.entries(t).flatMap(([key, val]) => Object.keys(val).length > 0 // if the current object is not "empty"
    ? cartesian([key], getAllKeyPaths(val)) // get the cartesian product of its child object's keys with this key
    : [[key]] // else, return just the current key 
  );
}

console.log(getAllKeyPaths(tDict));

您还可以尝试的另一种方法是回溯方法。下面，我首先获取对象的条目 

[[key, value], ...]
对。 对于每个键，我将键推入 
step
数组，通过递归调用 
helper
函数，继续使用子对象的键构建该数组。最终，当我击中没有键的子对象时，我将这个 
step
数组推入最终返回的 
res
数组中。每次我将一个键推入 
step
数组并且递归调用完成时，我还会在 
.pop()
数组上使用 
step
来有效地“撤消”我推入的最后一个键，允许构建下一次迭代
step
数组的另一种组合： 

const tDict = { "Causative": {}, "Emphasis": {}, "D-Necessity": { "Future": { "E-Necessity": {} }, "B-Necessity": { "Future": { "E-Necessity": {} }, "Purpose": { "Cause": { "Adversative": { "Mirative": {} } }, "Infinitive": {} } }, "E-Necessity": {}, "D-Possibility": { "D-Necessity": {} }, "Purpose": { "Cause": { "Adversative": { "Mirative": {} } }, "Infinitive": {} } }, "Pro-Verb": {}, "Progressive": { "Habitual": {}, "Imperfective": {}, "Present": {} } };

function getAllKeyPaths(obj) {
  const res = [];
  function helper(obj, [...step] = []) {
    const entries = Object.entries(obj);
    if(entries.length === 0 && step.length > 0) // checking step.length handles if `getAllKeyPaths()` is called with an empty object
      res.push(step);

    for(const [key, val] of entries) {
      step.push(key);
      helper(val, step, res);
      step.pop();
    }
  }
  helper(obj);
  return res;
}

console.log(getAllKeyPaths(tDict));

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.