Given two functions, generate all nested applications of the functions to a given order

I have two functions $$f$$ and $$g$$. Given some order parameter $$n$$, I want to created all nested applications of $$f$$ and $$g$$ and save them in a list. For example, for order 1 we will have {f(x),g(x)}. For order 2 we have {f(f((x)),f(g(x)),g(f(x)),g(g(x))} and so in. In general, for order $$n$$ the list should contain $$2^n$$ items.

Using Composition:

Clear["Global*"];

comps[flist_List, n_ /; n > 0] := Module[
{t = Tuples[flist, n]},
Fold[Composition, #]@x & /@ t
]


Usage:

comps[{f, g}, 1]


{f[x], g[x]}

comps[{f, g}, 2]


{f[f[x]], f[g[x]], g[f[x]], g[g[x]]}

comps[{f, g}, 4]


{f[f[f[f[x]]]], f[f[f[g[x]]]], f[f[g[f[x]]]], f[f[g[g[x]]]],
f[g[f[f[x]]]], f[g[f[g[x]]]], f[g[g[f[x]]]], f[g[g[g[x]]]],
g[f[f[f[x]]]], g[f[f[g[x]]]], g[f[g[f[x]]]], g[f[g[g[x]]]],
g[g[f[f[x]]]], g[g[f[g[x]]]], g[g[g[f[x]]]], g[g[g[g[x]]]]}

Also explore RightComposition.

• Thank you for the answer! I will wait a bit before deciding which answer to accept. Both seem to work fine... Commented Mar 26 at 2:07

First level

a = {f[x], g[x]};


Second level

b = Flatten @ Transpose @ Query[All, {f, g}] @ a


{f[f[x]], f[g[x]], g[f[x]], g[g[x]]}

Subsequent levels

nesting[x_, n_] := Nest[Flatten @* Query[All, {f, g}], x, n]

nesting[b, 1]

{f[f[f[x]]], g[f[f[x]]],
f[f[g[x]]], g[f[g[x]]],
f[g[f[x]]], g[g[f[x]]],
f[g[g[x]]], g[g[g[x]]]}

list = nesting[b, 2]

{f[f[f[f[x]]]], g[f[f[f[x]]]], f[g[f[f[x]]]], g[g[f[f[x]]]],
f[f[f[g[x]]]], g[f[f[g[x]]]], f[g[f[g[x]]]], g[g[f[g[x]]]],
f[f[g[f[x]]]], g[f[g[f[x]]]], f[g[g[f[x]]]], g[g[g[f[x]]]],
f[f[g[g[x]]]], g[f[g[g[x]]]], f[g[g[g[x]]]], g[g[g[g[x]]]]}


Another ordering:

SubsetMap[ReverseSort, SubsetMap[Sort, list, 1 ;; 8], 9 ;; 16]

{f[f[f[f[x]]]], f[f[f[g[x]]]], f[g[f[f[x]]]], f[g[f[g[x]]]],
g[f[f[f[x]]]], g[f[f[g[x]]]], g[g[f[f[x]]]], g[g[f[g[x]]]],
g[g[g[g[x]]]], g[g[g[f[x]]]], g[f[g[g[x]]]], g[f[g[f[x]]]],
f[g[g[g[x]]]], f[g[g[f[x]]]], f[f[g[g[x]]]], f[f[g[f[x]]]]}
`
• Thank you for the answer! I will wait a bit before deciding which answer to accept. Commented Mar 26 at 2:07