Consider this input array which represents a graph:
[
{"id":1,"prev":["NaN"]},
{"id":2,"prev":["NaN"]},
{"id":3,"prev":[1]},
{"id":4,"prev":[2]},
{"id":5,"prev":[2]},
{"id":6,"prev":[3,4]},
{"id":7,"prev":[5,6]}
]
My task is to find each possible option of ordering the elements in the list.
The order of the elements depends on whether the element has a previous one or not. For example, no. 7 will always be the last since it has 2 previous elements and no followers.
I tried to implement as follows but without success:
var possibleSolutions = [];
recursiveCheck(tasks.slice(), tasks.length, []);
function recursiveCheck(array, noCalls, currentSolution) {
var solution = currentSolution;
array.forEach((task, index, object) => {
if (task.prev.length <= 1 && isNaN(task.prev[0])) {
var tmpTasks = array.slice();
solution.push(task.id);
tmpTasks.splice(index, 1);
tmpTasks.forEach(el => {
el.prev.forEach((prevEl, index, object) => {
if (prevEl == task.id) {
object.splice(index, 1)
}
})
})
noCalls--;
if (noCalls == 0) {
possibleSolutions.push(solution)
solution = [];
} else {
recursiveCheck(tmpTasks, noCalls, solution);
}
}
});
}
This should be the output:
[
[1,2,3,4,5,6,7],
[1,2,3,4,6,5,7],
[1,2,3,5,4,6,7],
[1,2,4,3,5,6,7],
[1,2,4,3,6,5,7],
[1,2,4,5,3,6,7],
[1,2,5,3,4,6,7],
[1,2,5,4,3,6,7],
[1,3,2,4,5,6,7],
[1,3,2,4,6,5,7],
[1,3,2,5,4,6,7],
[2,1,3,4,5,6,7],
[2,1,3,4,6,5,7],
[2,1,3,5,4,6,7],
[2,1,4,3,5,6,7],
[2,1,4,3,6,5,7],
[2,1,4,5,3,6,7],
[2,1,5,3,4,6,7],
[2,1,5,4,3,6,7],
[2,4,1,3,5,6,7],
[2,4,1,3,6,5,7],
[2,4,1,5,3,6,7],
[2,4,5,1,3,6,7],
[2,5,1,3,4,6,7],
[2,5,1,4,3,6,7],
[2,5,4,1,3,6,7]
]
As another example, the array cannot be arranged like [1,3,6,...]
because 6 has a previous element 4 and therefore element 4 must be before 6.
Let's discuss this a bit more abstractly.
A directed graph is the data structure we're really taking as input here. We have a set V
of vertices/nodes and a set E
of edges. Each edge is an ordered pair (v1, v2)
, where v1
and v2
are both vertices, representing an arrow from v1
to v2
. Here, we're representing the graph using the "adjacency list" representation.
The task is to find all the ways to topologically sort this graph.
We can describe the ways to topologically sort a graph as follows:
If we want to topologically sort the empty graph (the graph with no vertices), this is easy: the only way to do it is to output the empty sorting []
. So the list of all ways to topologically sort the empty graph will be [[]]
.
Now, let's consider the problem of topologically sorting a non-empty graph. Consider a sequence s
which is a topological sort of a non-empty graph G
. We can consider the first element of s
, which we will call x
, and the sequence of all the rest of the elements, which we call s'
.
We know that x
must be a node in G
, and we know that x
cannot have any predecessors in G
. In other words, there can be no node y
such that (y, x)
is an edge.
We also know that s'
must be a topological sort of G'_x
, which is G
but with the node x
(and all edges connecting to it) removed.
So to get all the topological sortings of G
, we must find all sequences with initial element x
and remaining elements s'
, such that x
is an element of G
with no predecessors and s'
is a topological sorting of G'_x
.
const remove_node = (g, x) =>
g.flatMap((node) => node["id"] == x ?
[] :
{"id": node["id"],
"prev": node["prev"].filter((id) => id != x)});
const topological_sorts = (g) =>
g.length == 0 ?
[[]] :
g.filter((node) => node["prev"].length == 0)
.map((node) => node["id"])
.flatMap((id) =>
topological_sorts(remove_node(g, id)).map((sorting) =>
[id].concat(sorting)));
const remove_nan = (g) => g.map((node) =>
({ "id" : node.id,
"prev": node.prev.filter((predecessor) =>
predecessor !== "NaN") } ));
const get_answer = (g) => topological_sorts(remove_nan(g));
Calling get_answer
on your graph will result in the correct answer.