javascript - Java 到 JavaScript 类型转换算法

Question

我有以下功能，我想翻译成 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);

有人有什么想法吗？非常感谢。

Answer 1

主要问题是:

• 递归的终点(当 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 转换为数组的默认方式。