# What is a compact way to generate the list of $n^m$ composite functions, given a list of n functions and a composition depth of m?

Introduction.

An image says more than a thousand words. The functions sym4ref (pmm) and sym4rot (p4) create symmetries of a geometric object in the 2D Euclidean Space. ( pmm, p4 refer to the list of 17 Wallpaper Groups, see: https://en.wikipedia.org/wiki/List_of_planar_symmetry_groups#Wallpaper_groups ).

In the List ind I collected the 4 possible compositions of the two functions :

ind := {
Composition[sym4ref, sym4ref],
Composition[sym4ref, sym4rot],
Composition[sym4rot, sym4ref],
Composition[sym4rot, sym4rot]
}


such that I can simply iterate over them :

Table[ind[[k]][dpoly] // toGL // gr, {k, 1, 4}]


( The function toGL is an intermediary function which translates 'dpoly' in custom, tailor made, geometry code, to standard Mathematica code, gr is short for the standard Mathematica function Graphics )

So far, the practical application side of the problem.

Problem

The question is about generating an indexed list of composite functions like:

ind := {
Composition[sym4ref, sym4ref],
Composition[sym4ref, sym4rot],
Composition[sym4rot, sym4ref],
Composition[sym4rot, sym4rot]
}


Let's focus and make this a bit more abstract, but look at an example first. Let the list of functions of be ${f_1, f_2}$ and the requested composition length 3, in which case we would expect as result:

ind := {
Composition[f1, f1, f1],
Composition[f1, f1, f2],
Composition[f1, f2, f1],
Composition[f1, f2, f2],
Composition[f2, f1, f1],
Composition[f2, f1, f2],
Composition[f2, f2, f1],
Composition[f2, f2, f2]
}


Question

Now, assume a list of n functions, i.e. $f_1, f_2, ... f_n$, and a requested composition length of $m$.

What is the most ( read: a very ) compact way to code the generation of the list of $n^m$ composite functions, where the list of $n$ functions is given, as well as the requested composition depth $m$ ?

Reason

The reason for asking this question, and the emphasis on it, is compact functional code. I am always surprised, 'in awe', have much respect for the skill of writing compact functional code, a skill which I have not, and probably never have.

Or, going back to the introductory example:

Table[ind[[k]][dpoly] // toGL // gr, {k, 1, 4}]


I would like to do this as:

Table[g[funclist, m][[k]][dpoly] // toGL // gr, {k, 1, Length[g[funclist, m]]}]


where g is the function asked for.

Epilog • Something like this? Composition @@@ Tuples[Array[f, n], m]? – rhermans Jul 14 '18 at 11:04
• m, I understand, where is the input list of functions? – nilo de roock Jul 14 '18 at 11:09
• Indexed as {f,f,...} – rhermans Jul 14 '18 at 11:10
• So f is ind as in the example above ? Which is the request. – nilo de roock Jul 14 '18 at 11:12

## 1 Answer

If you want to receive a List of functions and an Integer, then

cmp[fl_List, m_Integer] := Composition @@@ Tuples[fl, m]

cmp[{f1, f2}, 3]
(* {f1@*f1@*f1, f1@*f1@*f2, f1@*f2@*f1, f1@*f2@*f2, f2@*f1@*f1, f2@*f1@*f2, f2@*f2@*f1, f2@*f2@*f2} *)


Or, after the comment by @CarlWoll,

cmp[fl_List, m_Integer] := Tuples[Composition @@ fl, m]


And since you did say most compact,

cmp[{f_, g___}, m_Integer] := Tuples[f@*g, m]


But at the time you are defining your functions, you could name them already with an indexed expression, and instead of {f1, f2, f3, f4, f5} you could have {f, f, f, f, f}. In that case,

Composition @@@ Tuples[Array[f, n], m]

• @MichaelE2 I think Tuples does support such syntactic sugar, e.g., you could use Tuples[Composition[f1,f2], 3] – Carl Woll Jul 14 '18 at 18:40
• It works as expected, thank you very much. – nilo de roock Jul 15 '18 at 7:28