我有以下功能,我想翻译成 JS(我对 JS 还是新手,所以有一些困难):
它获取一个包含 N 个节点的完整图,并枚举所有唯一的对匹配。
/**
*
* @param nodes The nodes still to be added to our edge list.
* @param edges The current edge list. This is mutated, so always return a clone!
*/
public static <N> List<Map<N,N>> enumerateEdges(List<N> nodes,Map<N,N> edges){
if(nodes.isEmpty()) // No more nodes to create edges from, so return our current edge list in a new list.
return Collections.singletonList(new HashMap<>(edges));
N start = nodes.get(0); //The start node of our next pair.
List<Map<N,N>> acc = new LinkedList<>(); //The accumulation of the EdgeLists
for(int i = 1; i<nodes.size(); ++i){
N end = nodes.get(i); //The end node of our pair
edges.put(start,end); //Add this pair to our edge list
List<N> unused = new ArrayList<>(nodes); // The nodes not used in our edge list.
unused.remove(i);
unused.remove(0);
acc.addAll(enumerateEdges(unused,edges));
edges.remove(start); //Remove this pair from our edge list.
}
return acc;
}
调用方式:
List<Map<Integer,Integer>> results = enumerateEdges(Arrays.asList(0,1,2,3),new HashMap<>());
我目前对此的尝试不起作用。它在执行 console.log()
时输出空数组。
function enumerateEdges(nodes, edges) {
if (nodes.length == 0) return [];
let start = nodes[0];
let acc = [];
for(let i = 1; i < nodes.length; i++) {
let end = nodes[i];
edges = [ {start,end} ];
let unused = nodes.slice(0);
unused.splice(i,1);
unused.splice(0,1);
acc.push.apply(acc, enumerateEdges(unused,edges));
edges.splice(0, 1);
}
return acc;
}
调用它:
let nodes = [1,2,3,4];
let edges = [];
enumerateEdges(nodes, edges);
有人有什么想法吗?非常感谢。
最佳答案
主要问题是:
- 递归的终点(当
nodes.length == 0
时)不应该返回空数组,而是 edges 数组的副本 -
edges = [ {start,end} ]
完全覆盖edges
中的内容前。你需要push
上面的那对。此外 -
edges.splice(0, 1)
删除第一个元素,但在原始代码中,它必须删除以 start 为键的元素,实际上它是 edges 列表中的最后一个元素。
注意 JavaScript 有一个 Map
可用于 edges
的构造函数,所以它很像 Java 代码的工作方式。但在这种情况下,我发现它的使用有点矫枉过正:数组就可以正常工作。我在第二个片段中使用 Map 添加了版本。
编辑:我还建议更改条件 length == 0
至 length < 2
,因此当您将奇数个节点传递给它时,它不会遇到麻烦。
function enumerateEdges(nodes, edges) {
if (nodes.length < 2) return [...edges]; // return copy
let start = nodes[0];
let acc = [];
for(let i = 1; i < nodes.length; i++) {
let end = nodes[i];
edges.push({start, end}); // don't overwrite, but push
let unused = nodes.slice(0);
unused.splice(i,1);
unused.splice(0,1);
// The spread operator will put each of the array elements as separate arguments
// ... so no more need for the mysterious apply:
acc.push(...enumerateEdges(unused, edges));
edges.pop(); // in practice it is always the last element to be removed
}
return acc;
}
let nodes = [1,2,3,4];
let edges = [];
let result = enumerateEdges(nodes, edges);
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
为了好玩,这是它的高度浓缩版本:
function enumerateEdges(nodes, edges) {
return nodes.length < 2 ? edges
: nodes.reduce( (acc, end, i) => (i<2 ? [] : acc).concat(
enumerateEdges(nodes.slice(1, i).concat(nodes.slice(i+1)),
[...edges, {start:nodes[0], end}])
) );
}
let nodes = [1,2,3,4];
let edges = [];
let result = enumerateEdges(nodes, edges);
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
map 的替代方案:
function enumerateEdges(nodes, edges) {
if (nodes.length < 2) return [...edges]; // return copy
let start = nodes[0];
let acc = [];
for(let i = 1; i < nodes.length; i++) {
let end = nodes[i];
edges.set(start, end); // <-- Map method to add
let unused = nodes.slice(0);
unused.splice(i,1);
unused.splice(0,1);
// The spread operator will put each of the array elements as separate arguments
// ... so no more need for the mysterious apply:
acc.push(...enumerateEdges(unused, edges));
edges.delete(start); // <-- Map method to remove
}
return acc;
}
let nodes = [1,2,3,4];
let edges = new Map(); // <-- use Map
let result = enumerateEdges(nodes, edges);
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
请注意,边现在作为简单的对数组输出,例如 [1, 2]
, 而不是 {start: 1, end: 2}
.这当然可以更改,但我保留了它——这是将 map 转换为数组的默认方式。
关于javascript - Java 到 JavaScript 类型转换算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40567972/