Suppose $(G,\cdot)$ is a group and $X \subset G$ is a nonempty set. The group generated by $X$ is a subgroup of $(G,\cdot)$ with carrier set
$$\langle X \rangle = \left\{ g_1^{i_1} \cdot \ldots \cdot g_k^{i_k} \, \middle| \, k \in \mathbb{N}, \; g_j \in X, \; i_j \in \mathbb{Z} \right\} .$$
For finite groups, this definition is unnecessarily complicated. Let's say that $|G| = n$, then
$$\langle X \rangle = \left\{ g_1^{i_1} \cdot \ldots \cdot g_k^{i_k} \, \middle| \, k \in \mathbb{N}, \; \color{darkred}{k \leq n}, \; g_j \in X, \; i_j \in \mathbb{N}, \; \color{darkred}{i_j \leq n} \right\} .$$
Suddenly, a computer would be able to generate the set, though it would make many redundant computations of the same elements.
We can do better. Let's denote $\operatorname{ord} (g)$ the order of $g \in G$ in $(G,\cdot)$, then
$$\langle X \rangle = \left\{ g_1^{i_1} \cdot \ldots \cdot g_k^{i_k} \, \middle| \, k \in \mathbb{N}, \; k \leq n, \; g_j \in X, \; i_j \in \mathbb{N}, \; \color{darkred}{i_j < \operatorname{ord} (g_j)} \right\} .$$
What is the most "efficient" (in the sense that it would on average generate each element the least amount of times) way of writing such definition? How far can we go?
I can't really tell if this problem is an obvious one or if it is something hard. Recommending some literature would be aslo very appreciated.
Here's one option: For a finite group $(G,\cdot)$ and nonempty subset $X \subset G$, define $Y_0 = \{1_G\}$, $Y_1 = X$, and $$ Y_{k+1} = \left\{ \space f \cdot g \, \middle| \, f \in X,\; g \in Y_k \right\} \setminus \bigcup_{i=0}^{k} Y_i $$
Because the group is finite, for some $n$ all sets after $Y_n$ are empty, and the result is $$\langle X \rangle = \bigcup_{i=0}^n Y_i$$
This is essentially a breadth-first search algorithm: $Y_k$ contains the new nodes found during step $k$, and $\bigcup_{i=0}^{k} Y_i$ all nodes found by that step. The next step then finds any neighbors of the new nodes that had not been found before.
The question asked for a definition that "would on average generate each element the least amount of times", so lets evaluate: The sequence of $Y_k$ is a partition of $\langle X \rangle$, so each element of $\langle X \rangle$ is multiplied exactly once with every element of $X$ and there are a total of $|X| |\langle X \rangle|$ evaluations of $ f \cdot g $. The clear minimum would be $|\langle X \rangle|$, so at least for small $X$ we're not far off.
edit: This would be inefficient if X is not a minimal generating set. If that's a possibility, we can augment the above to iteratively add generators:
Pick any $g_0 \in X$, and compute $Z_0 = \langle g_0 \rangle$ as above. Then, iteratively compute each $Z_i = \langle g_0,g_1,...,g_i \rangle$ starting from $Z_{i-1}$ instead of $\{1_G\}$, and picking $g_i$ from $X \setminus Z_{i-1}$. The result is the $Z_k$ that contains all of $X$.