Java to JavaScript Type Conversion Algorithm

Question

I have the following function that I would like to translate to JS (I am still new to JS, so having some difficulty):

It takes a complete graph of N nodes and enumerates all the unique pair matchings.

/**
*
* @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;
}

Called with:

List<Map<Integer,Integer>> results = enumerateEdges(Arrays.asList(0,1,2,3),new HashMap<>());

My current attempt at this doesn't work. It outputs empty arrays when doing a 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;
}

Calling this with:

let nodes = [1,2,3,4];
let edges = [];
enumerateEdges(nodes, edges);

Does anyone have any ideas? Much appreciated.

Answer 1

The main issues are:

• The end point of the recursion (when nodes.length == 0) should not return an empty array, but a copy of the edges array
• edges = [ {start,end} ] completely overwrites whatever was in edges before. You need to push the pair on it. Furthermore
• edges.splice(0, 1) removes the first element, but in the original code it must remove the element keyed by start, which in practice is the last element in the edges list.

Note that JavaScript has a Map constructor which you could use for edges, so it would be much like how the Java code works. But in this case I find its use overkill: an array will just work fine. I added the version using Map in a second snippet.

Edit: I would also suggest to change the condition length == 0 to length < 2, so the thing doesn't get into trouble when you pass it an odd number of nodes.

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; }

For fun, here is a highly condensed version of it:

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; }

Alternative with 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; }

Note that the edges are now output as simple pair-arrays, like [1, 2], instead of {start: 1, end: 2}. This can of course be changed, but I left it like this -- it is the default way on how Maps are translated to arrays.