cyberkronos - 1 year ago 57

Java 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 Source

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.

```
function enumerateEdges(nodes, edges) {
if (nodes.length == 0) 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; }`