I asked a related question here a few days ago, but this question is really wholly different.
Let $S_n$ be the symmetric group. My question is, does there exist a subset $A$ of $S_n$ such that for every element $\sigma \in S_n$, $\sigma$ can be "constructed" by taking subsets of the elements in $A$ and permuting those subsets so that the corresponding composition equals $\sigma$?
That is, I want a subset $A \subset S_n$ such that any element of $S_n$ can be represented as a composition of some subset of elements of $A$ where each element of $A$ appears at most once in this composition. If we take $|A|=m \geq n$, then we have $$ \sum_{i=1}^m {m \choose i} i! \geq n! $$ different possible subsets/permutations, so if $A$ is sufficiently large there should be enough "space" to "generate" $S_n$, but how can you construct such a set? And what would be the smallest possible $m$?
More formally, let $A = \{\sigma_1,...,\sigma_m\}$ be a subset of $S_n$ with $m \geq n$. Then does there exist an $A$ such that for every $\sigma \in S_n$, there is a $B \subseteq A$ with $B = \{\sigma_{a_1},...,\sigma_{a_k}\}$, $k \leq m$, and a permutation of the elements in $B$, call it $\sigma^* \in S_k$, so that if $\sigma^*(a_1,a_2,...,a_k) = (b_1,b_2,...,b_k)$ then $$ \sigma_{b_1}\circ \sigma_{b_2} \circ \cdots \sigma_{b_k} = \sigma? $$ And if such a set $A$ does exist, what is the smallest possible $m$ for which such a set could be constructed?