Let $G < S_n$ be a permutation group of degree $n$, $\mathcal{P(n)}$ denote the set of all partitions of $n$, and $c: G \rightarrow \mathcal{P}(n)$, where $c(g)$ is the partition given by the multiset of cycle lengths of $g$. Define the profile (is there a standard term for this?) of $G$ to be the map $P: \mathcal{P}(n) \rightarrow \mathbb{N} \cup \{0\}$ where $P(\pi) = \#\{g \in G: c(g) = \pi\}$ is the number of elements of $G$ whose multiset of cycle lengths is $\pi$.
Question: Is there a pair of non-conjugate subgroups $G, H < S_n$ with the same profile?
In these questions I'm assuming that a subgroup $G < S_n$ is specified by giving a list of generators. When I ask for a "good" algorithm I mean one that is subexhaustive. Ideally it should run in time polynomial in $n$. For example, a lot of group theoretic calculations have good algorithms using the Schreier-Sims algorithm (and variants).
Question: Given a subgroup $G < S_n$ is there a good algorithm to compute $P(\pi)$ for a given partition $\pi$? It's easy to do this "by hand" for $S_n$ and $A_n$.
Question: We are given a subgroup $G < S_n$, and $h \in S_n$, $h \not \in G$. For every partition $\pi \in \mathcal{P}(n)$, is there a good algorithm which either determines that there is no $g \in h G$ with $c(g) = \pi$, or if there is such a $g$, constructs one?
Added: The motivation for this problem is the following: I was given pairs $(h, G)$, where $h \in S_n$, and $G < S_n$ is a subgroup with $h \not \in G$. I wanted to find a $g \in G$ so that ${\tt cycles}(gh)$ was maximal among all choices of $g \in G$, where ${\tt cycles}(g)$ means the number of cycles in $g$ (including trivial ones). I had thought of exhausting over all partitions for this. In some of the examples the order of $G$ was small enough to exhaust over, but in others it was huge.
