Permutation acting on subsets of the domain

Question

Suppose a group $G \subseteq S_n$, where $S_n$ is the permutation group on $X = \{1, ... ,n\}$. Consider two subsets $Y,Z \subseteq X$ with $|Y| = |Z| \leq n$.

Problem: Is there a permutation $g \in G$ that maps $g(Y) = Z$, i.e. $g(y) \in Z \; \forall y \in Y$ ?

I'm looking for an efficient method to check if there exists such a $g \in G$.

My current solution to this, is a simple iteration over all elements $g$ and checking if the permutation maps $Y \rightarrow Z$. I was wondering if there exists a more efficient method, which I could use (e.g. in GAP). My background is not in Group Theory, so I might be missing the correct term for this problem.

Answer 1

A practical method for testing whether one set can be mapped to another by a permutation is a backtrack search. (Whether it is efficient depends on your definition -- it is not polynomial time and as far as I know no general polynomial time method is known.) It uses the group structure (and conditions on where points must get mapped) to avoid testing all group elements. In practice, it performs quite well in most cases.

In GAP, you can find such elements using RepresentativeAction, specifying an action OnSets (which in GAP must be sorted lists):

gap> G:=Group((1,2,3,4,5),(1,2,3));;
gap> RepresentativeAction(G,[1,3,4],[2,4,5],OnSets);
(1,2)(3,5)