I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected graphs with multiple identical connected components, and each connected component also has an automorphism group of its own). These automorphisms induce equivalence relations between $\pi$'s. I am computing a sum $\sum_\pi f(\pi)$ where the function $f$ is constant on each equivalence class of $\pi$'s. The function $f$ is expensive to evaluate, so I want to group equivalent terms in this sum to have fewer terms to deal with.
So I need to divide all maps $\pi$ into a small number of groups $P_i$ so that within each $P_i$ the maps are equivalent up to applying the graph automorphisms. For each $P_i$ I need to know a representative, and its cardinality $n_i$ (so that $\sum n_i=N!$). Now, I imagine that finding the minimal possible number of $P_i$'s is a hard problem (this would be the problem of understanding the structure of double coset space $G_1\backslash S_N/G_2$, where $G_i$ are the automorphism groups of $\Gamma_i$.)
But in practice I don't need the full classification of equivalence classes, I just need that the total number of $P_i$'s be not too large. I am wondering if there is a systematic algorithm which inexpensively produces a rough grouping of terms (say using the simplest connected components), and with more running time produces a slightly better grouping etc. I will then decide myself when to terminate the grouping process and switch to the sum evaluation.
More specific information: My graphs are subject to the condition $N/2+2E<\Delta$, where $N$ and $E$ are the number of nodes and edges and $\Delta=16\div 20$. In particular no connected component has more than 10 nodes, but the total number of nodes can be as much as 40 provided that they are all disconnected. Saving the full $S_N$ in memory and working on it is impractical, but once one separates out fully disconnected single vertices, and other simple connected components, it starts looking practical.
The function $f$ depends on the global structure of the graphs and of the map. It is not a polynomial in the variables $x_{ij}$ that Joshua mentions in his comment below. I doubt it will help, but I will provide more details. One associates a particular $D$-dimensional tensor with each pair of vertices connected by $\pi$. The tensor has $d_i+d_j$ indices where $d_i$ and $d_j$ are the degrees of the vertices. The $f$ is a number obtained by contracting indices of all the tensors along the graph edges.
