如何用C语言计算Sₙ中D₂ₙ的陪集？求参考Python实现思路

Hey there! Let's break down how to tackle this problem, starting with core concepts, then unpacking the Python implementation logic, and finally adapting it to C.

First: Recapping the Group Definitions #

Just to make sure we're aligned:

• $S_n$ is the symmetric group of all permutations of $n$ elements. Each permutation can be written as a rearrangement of ${1,2,...,n}$ or using cycle notation.
• $D_{2n}$ (the dihedral group) represents the symmetries of a regular $n$-gon, with exactly $2n$ elements. It's generated by two elements:
  • Rotation $r = (1\ 2\ 3\ \dots\ n)$: a cyclic shift of all elements by one position.
  • Reflection $s = (1\ n)(2\ n-1)\dots$: a flip over the axis through the center and either vertex 1 (odd $n$) or the midpoint of edge 1-$n$ (even $n$).

Core Coset Calculation Logic (Works for Python or C) #

No matter the language, finding all left cosets $gD_{2n}$ (where $g \in S_n$) follows these key steps:

1. Generate all elements of $D_{2n}$: Since $D_{2n}$ has $2n$ elements, build this set by creating all rotations ($r^k$ for $k = 0,1,...,n-1$) and all reflections ($r^k s$ for $k = 0,1,...,n-1$).
2. Enumerate cosets via equivalence classes:
   • Track which permutations have already been assigned to a coset.
   • For each unmarked permutation $g$ in $S_n$:
     • Compute the coset ${g \cdot d \mid d \in D_{2n}}$ (where $\cdot$ is permutation multiplication).
     • Mark all permutations in this coset as "visited".
     • Store $g$ as the representative of this coset.

Understanding the $S_6$/$D_{12}$ Python Implementation #

The Python code you saw likely followed this exact blueprint:

• It first generated the 12 elements of $D_{12}$ by iterating through rotations and reflections (using tuples to represent permutations, since they're hashable and easy to store in sets).
• It looped through all permutations of ${1,2,...,6}$, using a set to track visited permutations.
• For each unvisited permutation, it multiplied it by every element of $D_{12}$ to get the full coset, added those permutations to the visited set, and stored the coset for output.

Adapting This to C #

C doesn't have built-in permutation types or hash sets, so we'll need to build our own tools:

1. Representing Permutations #

Use a 1-based integer array (to match our element numbering from 1 to $n$) where perm[i] is the image of element $i$. For example, the rotation $r = (1234)$ would be [0,2,3,4,1] (index 0 is unused for clarity).

2. Implement Permutation Multiplication #

Permutation multiplication is function composition: if we have permutations $a$ and $b$, the product $a \cdot b$ means $(a \cdot b)(x) = a(b(x))$. Here's a quick function sketch:

void multiply_perms(int n, int* a, int* b, int* result) {
    for (int x = 1; x <= n; x++) {
        result[x] = a[b[x]];
    }
}

3. Generate $D_{2n}$ Elements #

• First, create the base rotation permutation $r$.
• Generate all rotations: start with the identity permutation ($r^0$), then repeatedly multiply by $r$ to get $r^1, r^2, ..., r^{n-1}$.
• Create the reflection permutation $s$.
• Generate all reflections: multiply each rotation by $s$ (remember permutation order matters—left cosets use $g \cdot d$, so reflections are $r^k \cdot s$).

4. Track Visited Permutations #

Since permutations are arrays, we can't hash them directly. Instead, for small $n$:

• Convert each permutation to a unique integer (e.g., treat the permutation as a base-$n$ number).
• Use a boolean array or bitmask to mark which permutations have been visited.

5. Enumerate Cosets #

Loop through all possible permutations of ${1,...,n}$ (use a backtracking function to generate permutations in order). For each unvisited permutation:

• Multiply it by every element in $D_{2n}$ to get the coset elements.
• Mark each coset element as visited.
• Store the coset (e.g., as a list of permutation arrays).

Posting Math Symbols on Stack Overflow #

Stack Overflow supports LaTeX-style math notation using dollar signs:

• Inline math: Wrap formulas in single dollar signs, e.g., $S_n$, $D_{2n}$, $(1\ 2\ 3\ \dots\ n)$.
• Block math: Use double dollar signs for larger equations:
  $$
  r = (1\ 2\ 3\ \dots\ n), \quad s = (1\ n)(2\ n-1)\dots
  $$
  Standard LaTeX commands work for cycle notation, subscripts, and more—most editors handle backslashes automatically, but double-check if your notation isn't rendering correctly.

内容的提问来源于stack exchange，提问作者smita