Two notable problems involving permutation group subgroups are determining the subgroup order (e.g., LOJ177) and counting inversions (e.g., Grupa Permutacji). Surprisingly, both admit polynomial-time solutions, leveraging a key property of "uniformity" in the generated subgroup.

Uniformity of Subgroup Permutations

For a subgroup generated by a set of permutations, consider the possible values of ( p_i ) (the ( i )-th element of a permutation in the subgroup). If ( p_i ) has ( k ) distinct values ( a_1, \dots, a_k ), each value occurs in exactly the same number of permutations. This holds for tuples of positions (e.g., ( (p_i, p_j) )): all possible tuples in the subgroup’s permutations are equally likely.

Inversion Count (Grupa Permutacji)

Inversions are tuples ( (i,j) ) with ( i<j ) and ( p_i > p_j ). For each generator permutation, we connect ( (i,j) \leftrightarrow (p_i, p_j) ) with bidirectional edges. Each connected component of this graph contains ( a ) (( i<j ) tuples) and ( b ) (( i>j ) tuples). The probability of an inversion from an ( i<j ) tuple is ( \frac{b}{a+b} ), so the total contribution per component is ( \frac{ab}{a+b} ). This gives an ( O(n^3) ) algorithm.

Uniformity Proof via Graphs

To justify uniformity, model tuples (e.g., ( (\alpha_1, \dots, \alpha_m) )) as nodes. For each generator permutation ( s ), add an edge from ( (\alpha_1, \dots, \alpha_m) ) to ( (s(\alpha_1), \dots, s(\alpha_m)) ), with ( s ) as the edge weight. A reverse edge (with ( s^{-1} )) ensures the graph is undirected (or treat it as directed). Traversing this graph via DFS shows all reachable tuples (values) are equally likely.

Subgroup Order (LOJ177)

To compute the subgroup size, first count the number of distinct ( p_n ) values. Then, recursively solve for permutations where ( p_n = n ) (reducing the problem to ( n-1 ) elements). The key is reducing the generator set size to ( O(n) ) (via random sampling), leading to an ( O(n^5) ) algorithm.

Code Examples

Grupa Permutacji (Inversion Count)

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int MOD = 1e9+7;
int n, k;
int gen[N][N]; // Generators (k permutations of size n)
int parent[N*N];
int cntA[N*N], cntB[N*N]; // Counts for (i<j) and (i>j) in each component

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

int main() {
    n = read(), k = read();
    for (int i=0; i<k; ++i)
        for (int j=0; j<n; ++j)
            gen[i][j] = read() - 1; // Convert to 0-based
    
    int total = n * n;
    for (int i=0; i<total; ++i) parent[i] = i;
    
    const int L = 20; // Random iterations
    for (int it=0; it<L; ++it) {
        int perm[N];
        for (int j=0; j<n; ++j) perm[j] = j;
        for (int i=0; i<k; ++i) {
            if (rand() % 2) { // Randomly apply generator
                int tmp[N];
                for (int j=0; j<n; ++j) tmp[perm[j]] = gen[i][j];
                for (int j=0; j<n; ++j) perm[j] = tmp[j];
            }
        }
        // Union (i,j) with (perm[i], perm[j])
        auto get_id = [&](int x, int y) { return x * n + y; };
        for (int i=0; i<n; ++i)
            for (int j=0; j<n; ++j) {
                if (i == j) continue;
                int u = get_id(i, j), v = get_id(perm[i], perm[j]);
                parent[find(u)] = find(v);
            }
    }
    
    // Count a (i<j) and b (i>j) in each component
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j) {
            if (i == j) continue;
            int root = find(get_id(i, j));
            if (i < j) cntA[root]++;
            else cntB[root]++;
        }
    
    // Compute modular inverse
    vector<int> inv(total + 1);
    inv[1] = 1;
    for (int i=2; i<=total; ++i)
        inv[i] = (long long)(MOD - MOD/i) * inv[MOD%i] % MOD;
    
    int ans = 0;
    for (int i=0; i<total; ++i) {
        if (find(i) == i && cntA[i] && cntB[i]) {
            long long contrib = (long long)cntA[i] * cntB[i] % MOD;
            contrib = contrib * inv[cntA[i] + cntB[i]] % MOD;
            ans = (ans + contrib) % MOD;
        }
    }
    cout << ans << endl;
    return 0;
}

LOJ177 (Subgroup Order)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 20;
const int B = 20; // Generator reduction iterations

struct Perm {
    int p[MAXN];
    Perm() { for (int i=0; i<MAXN; ++i) p[i] = i; }
    Perm operator+(const Perm& o) const {
        Perm res;
        for (int i=0; i<MAXN; ++i) res.p[i] = o.p[p[i]];
        return res;
    }
    Perm inv() const {
        Perm res;
        for (int i=0; i<MAXN; ++i) res.p[p[i]] = i;
        return res;
    }
};

Perm a[MAXN], b[MAXN], path[MAXN * 2];
vector<pair<int, int>> adj[MAXN];
ll res[10], carry;
int len, num;
bool vis[MAXN];

void dfs(int u, Perm cur) {
    path[u] = cur;
    vis[u] = true;
    num++;
    for (auto [v, idx] : adj[u]) {
        if (!vis[v]) dfs(v, cur + a[idx]);
    }
}

void reduce_generators(int& n, int& m) {
    // Build adjacency list
    for (int i=0; i<m; ++i)
        for (int j=0; j<n; ++j)
            adj[j].emplace_back(a[i].p[j], i);
    
    Perm init; // Identity permutation
    dfs(n-1, init); // Start from n-1 (0-based)
    
    // Add inverse paths
    for (int i=0; i<n; ++i) {
        path[i + n] = path[i].inv();
        adj[i].clear();
    }
    
    // Generate new generators via random sampling
    for (int it=0; it<B; ++it) {
        b[it] = Perm(); // Identity
        for (int i=0; i<m; ++i)
            for (int j=0; j<n; ++j)
                if (vis[j] && (rand() % 2))
                    b[it] = b[it] + path[j] + a[i] + path[a[i].p[j] + n];
    }
    
    // Update generators
    m = B;
    for (int i=0; i<m; ++i) a[i] = b[i];
    
    // Update result (multiply by num, handle carry)
    carry = 0;
    for (int i=0; i<=len; ++i) {
        res[i] = res[i] * num + carry;
        carry = res[i] / 10000000000000000000LL;
        res[i] %= 10000000000000000000LL;
    }
    if (carry) res[++len] = carry;
    
    // Reset for next iteration
    memset(vis, 0, sizeof(vis));
    num = 0;
}

int main() {
    int n, m0;
    n = read(), m0 = read();
    for (int i=0; i<m0; ++i)
        for (int j=0; j<n; ++j)
            a[i].p[j] = read() - 1; // 0-based
    
    res[len=0] = 1;
    while (n > 0) {
        reduce_generators(n, m0);
        n--;
    }
    
    // Output result
    cout << res[len];
    for (int i=len-1; i>=0; --i)
        printf("%016lld", res[i]);
    cout << endl;
    return 0;
}