# Sorting a list of functions by exploiting the recursive structure

Given a list of functions list and a vector of arguments {t, a}:

list = {
h = f[t, x, y, z, a],
x = f[a, b],
p = f[r, n, t, g],
r = f[b, h, z],
n = f[z, h, r, t],
b = f[t],
z = f[x, y, a],
y = f[x, a, b],
}


I like to sort list by exploiting the Recursive structure of the functions in list. The expected outcome should be of the form:

List1 = {
b = f[t],
x = f[a, b],
y = f[x, a, b],
z = f[x, y, a],
h = f[t, x, y, z, a],
r = f[b, h, z],
n = f[z, h, r, t]
}


Note that p = f[r, n, t, g] is not included in the final output as g is not known.

Defining a function taking on two inputs: a given list of arguments v ={t, a} and an unordered l = list might be an option to automate the operation of interest. Such as

orderedF[v_, l_]:=...


If any of the function(s) in list does not have a sufficient number of predetermined arguments, then that function should be excluded from the final list to be generated. Namely, orderedF[] should only give a list of functions with arguments which are all predetermined. Those functions with an insufficient number of predetermined arguments should be identified as a separate list of functions.

EDIT More detailed sorting rule:

1. That t is already known fully identifies b=f[t];
2. That a, b are known fully identifies x = f[a, b];
3. That a, b, x are known fully identifies y = f[x, a, b] and so on;
4. That g is not known at all makes p = f[r, n, t, g] as an undetermined function, which should be kept out of the final outcome list.
• Can you explain the sorting rule in more detail? I don't understand how you got that output. I don't understand the significance of v = {t, a}. Nov 8, 2023 at 18:47
• What do you mean by "predetermined arguments"? Nov 8, 2023 at 18:50
• @lericr: Predetermined argument means that it has already given, which is known. Nov 8, 2023 at 18:56
• you said p shouldn't be in the list, but it is in your expected outcome. Nov 8, 2023 at 18:58
• @lericr: v = {t, a} denotes a given (predetermined) vector, which I like to use it in the orderedF[v_, l_]:=.... I just wanted to show that this function should take a vector and a list as inputs. Nov 8, 2023 at 18:58

## 2 Answers

Just and idea about using graphs in order to better visualize the problem:

Borrowing the list definition from @lericr.

v = {a, t}; (*initial known values*)
list = {h->f[t,x,y,z,a],x->f[a,b],p->f[r,n,t,g],r->f[b,h,z],n->f[z,h,r,t],b->f[t],z->f[x,y,a],y->f[x,a,b]};


Constructing the graph based on the relation between keys & f@arguments:

edges = Sequence @@@ KeyValueMap[{k, v} |-> k -> # & /@ v, <|list|>] ;
vertices = Union[Keys@#, Values@#] &[<|edges|>] ;
graph = Graph[edges
, VertexLabels -> Thread[vertices -> (Placed[#, Center] & /@ vertices)]
, VertexLabelStyle -> {Directive[14, Black, Bold]}
, VertexSize -> .5
, VertexStyle -> Thread[vertices -> (If[MemberQ[v, #], Green, Red] & /@ vertices)]
]


Looking up invalid nodes:

leafNodes = Flatten@Cases[VertexOutComponent[graph, #, 1] & /@ VertexList@graph
, c_ /; Length@c == 1 && FreeQ[List /@ v, c]];
invalidNodes = NestWhile[
Union@Flatten [({vertex} |-> Complement[VertexInComponent[graph, vertex, 1], v]) /@ #] &
, leafNodes, UnsameQ, 2];
HighlightGraph[graph, invalidNodes]


Cutting out the valid nodes & generating the list ordering:

validGraph = VertexDelete[graph, invalidNodes]
tsort = Reverse@TopologicalSort@validGraph
result = # -> <|list|>[#] & /@
Select[tsort
, ! FreeQ[Keys@<|list|>, #] && ContainsAll[tsort, List @@ <|list|>[#]] &]


(* filtered & sorted list *)
{b->f[t],x->f[a,b],y->f[x,a,b],z->f[x,y,a],h->f[t,x,y,z,a],r->f[b,h,z],n->f[z,h,r,t]}


Testing other initial configurations:

v = {a, z, b}; (*initial known values*)
{x->f[a,b],y->f[x,a,b],z->f[x,y,a]}


v = {a, z}; (*initial known values*)
{}


• OHHH! This actually makes it so much clearer (assuming this interpretion is what the OP wanted). I was interpreting the question "backwards". Excellent! Nov 9, 2023 at 23:41
• @lericr Thx, glad it helped (assuming of course that this is the way it should work :-) ) . Nov 10, 2023 at 0:11
• @vindobona: It is an inspiring approach! Your answer does not fully answer the question. The recursive structure of the functions is not utilized completely. For example, given v = {a, z, b}, you find x=f(.) and y=(.) but then {x,y,a} determines the function z=f(x,y,a), which is missing in your answer. Note that the vector v refers to only arguments (range) not the output (domain). The recursive structure would lead to 3 functions, not 2 as in your answer. Thanks again for your efforts. Nov 10, 2023 at 0:58
• @TugrulTemel I changed the criteria for the nodes selection in order to adapt it to your requirements (the v = {a,z,b}  case mentioned above) . result = # -> <|list|>[#] & /@ Select[tsort , ! FreeQ[Keys@<|list|>, #] && ContainsAll[tsort, List @@ <|list|>[#]] &] Nov 10, 2023 at 6:38
• @vindobona: Thank you very much for the code with an inspiring approach. I works just fine... Nov 10, 2023 at 15:31

I still don't understand the sorting, but here's a selector.

I redefined your lists like this:

list = {h -> f[t, x, y, z, a], x -> f[a, b], p -> f[r, n, t, g], r -> f[b, h, z], n -> f[z, h, r, t], b -> f[t], z -> f[x, y, a], y -> f[x, a, b]};
expected = {b -> f[t], x -> f[a, b], y -> f[x, a, b], z -> f[x, y, a], h -> f[t, x, y, z, a], r -> f[b, h, z], n -> f[z, h, r, t]};


This makes it much easier since the Set (=) will interfere with our ability to inspect things. Here's the selector:

selectF[list_, args_] :=
With[
{matcher = f[Alternatives @@ Flatten[{_f, args}] ...]},
Select[list, MatchQ[matcher]@*Last@*ReplaceRepeated[list]]]


Demonstration:

actual = selectF[list, {t, a}]
(* {h->f[t,x,y,z,a],x->f[a,b],r->f[b,h,z],n->f[z,h,r,t],b->f[t],z->f[x,y,a],y->f[x,a,b]} *)

ContainsExactly[actual, expected]
(* True *)


Update

I think maybe the sorting can be done just by looking at Depth:

selectF[list_, args_] :=
With[
{matcher = f[Alternatives @@ Flatten[{_f, args}] ...]},
SortBy[
Select[list, MatchQ[matcher]@*Last@*ReplaceRepeated[list]],
Depth@*ReplaceRepeated[list]@*Last]]


I didn't take the time to figure out how to reduce the duplication of the ReplaceRepeated computation.

• I did some trials. selectF[] function is not really performing in the way I expected. Can you give several examples to show how you use that function. The outputs of trials are not meeting the criteria I listed. Thank you for your effort. Nov 8, 2023 at 20:32
• If you mean the sorting, I already said that I don't understand your sorting rules. But as for matching the expected output as a set, the function works for me. Nov 8, 2023 at 20:39
• Would you consider to explain what is working in your code and what is not working in it? In my trials, selectF[list, {a, z}] generates an output not in line with the sorting because r function has an unknown argument h. Nov 8, 2023 at 21:08
• With a given vector {a, z, b}, still the updated selectF chooses r function, although this function has an unknown h. This implies that r function should not be part of the output. Nov 8, 2023 at 21:18
• But also, this isn't my problem. It's yours. I've given you some code that seems to do something similar to what you want. Maybe you should spend time tweaking it to see if you can get what you want. Or spend some time clarifying your question. I'm not taking homework assignments from you. I'm just trying to help you, and you seem to be unable to help us move this along together. But as I said, not my problem. Nov 8, 2023 at 22:23