Find subgroups of Sn - A program method

Posted on In ,

It is tedious to enumerate all of the subgroups of a symmetric group, such as \(S_4\). And I wrote a program to automate it.

This is one of the problem I met in the book Abstract Algebra - Theory and Applications, 2018, Thomas Judson:

CHAPTER 5. List all of the subgroups of \(S_4\).

Well, though this problem is quite easy (but heavily tedious), I would like to find a method that automate this task. Then I use the algorithm as follows:

  • Get distinct \(\langle g\rangle\) for \(g\in S_n\).
  • All of the subgroups contains several cyclic groups. Then I use \(O(2^m)\) (where \(m\) is the number of distinct cyclic subgroups of \(S_n\)) to enumerate which cyclic subgroups are necessarily inside a new group we want to generate.
  • Then we need to combine these cyclic group to get the bigger group (and we require that it is as small as possible to avoid missing solutions). This could be done to use \(X=A_1\cup A_2\cup\cdots A_k\) at the beginning, and repeat \(X:=XX\) until it converges.

And the C++ code is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <cassert>

/*
 * Pn: Denote a permutation of size n.
 * elements in range [0, n)
 */
class Pn {
public:
  using size_type = std::vector<int>::size_type;
  Pn(const std::vector<int> &i) : n(i.size()), p(i) {}
  size_type get_n() const { return n; }
private:
  size_type n = 0;
  std::vector<int> p;

  friend bool operator < (const Pn &a, const Pn &b);
  friend bool operator == (const Pn &a, const Pn &b);
  friend Pn operator * (const Pn &a, const Pn &b);
  friend std::ostream& operator << (std::ostream &os, const Pn &x);
};
bool operator < (const Pn &a, const Pn &b) {
  assert(a.n == b.n);
  for (Pn::size_type i = 0; i != a.n; ++i)
    if (a.p[i] != b.p[i])
      return a.p[i] < b.p[i];
  return false;
}
bool operator == (const Pn &a, const Pn &b) {
  assert(a.n == b.n);
  for (Pn::size_type i = 0; i != a.n; ++i)
    if (a.p[i] != b.p[i])
      return false;
  return true;
}
Pn operator * (const Pn &a, const Pn &b) {
  assert(a.n == b.n);
  std::vector<int> ret(a.n);
  for (Pn::size_type i = 0; i != a.n; ++i)
    ret[i] = a.p[b.p[i]];
  return Pn(ret);
}
std::ostream& operator << (std::ostream &os, const Pn &x) {
  std::set<int> outputed;
  bool isoutput = false;
  for (Pn::size_type i = 0; i != x.get_n(); i++) {
    if (x.p[i] == (int)i || outputed.count(i))
      continue;
    int now = i;
    os << "(";
    while (!outputed.count(now)) {
      outputed.insert(now);
      os << now + 1;
      now = x.p[now];
    }
    os << ")";
    isoutput = true;
  }
  if (!isoutput)
    os << "(1)";
  return os;
}
Pn Pn_identity(Pn::size_type n) {
  std::vector<int> id;
  for (Pn::size_type i = 0; i != n; ++i)
    id.push_back(i);
  return Pn(id);
}
/*
 * Gn: a subgroup of Sn
 */

class Gn {
public:
  using size_type = Pn::size_type;
  using iterator = std::set<Pn>::iterator;
  using const_iterator = std::set<Pn>::const_iterator;
  Gn(size_type n) : n(n) {}
  size_type get_n() const { return n; }
  size_type get_size() const { return eles.size(); }
  void insert(const Pn &x);
  void insert(const Gn &x);
  iterator begin() { return eles.begin(); }
  const_iterator begin() const { return eles.begin(); }
  iterator end()   { return eles.end(); }
  const_iterator end() const { return eles.end(); }
private:
  std::set<Pn> eles;
  size_type n = 0;

  friend Gn gen_all(size_type n);
  friend Gn gen_cycle(Pn g);
  friend bool operator < (const Gn &a, const Gn &b);
  friend bool operator == (const Gn &a, const Gn &b);
  friend std::ostream& operator << (std::ostream &os, const Gn &x);
  friend Gn operator * (const Gn &a, const Gn &b);
};

void Gn::insert(const Pn &x) {
  assert(n == x.get_n());
  eles.emplace(x);
}
void Gn::insert(const Gn &x) {
  assert(n == x.get_n());
  for (const auto &v : x)
    insert(v);
}
void gen_all_perms(Gn::size_type n, Gn::size_type steps, std::set<Pn> &eles,
    std::vector<int> &used, std::vector<int> &now) {
  if (steps == n) {
    eles.insert(now);
    return ;
  }
  for (Gn::size_type i = 0; i != n; ++i)
    if (!used[i]) {
      now.push_back(i);
      used[i] = 1;
      gen_all_perms(n, steps + 1, eles, used, now);
      used[i] = 0;
      now.pop_back();
    }
}
Gn gen_all(Gn::size_type n) {
  Gn ret(n);
  std::vector<int> used(n), now;
  gen_all_perms(n, 0, ret.eles, used, now);
  return ret;
}
Gn gen_id(Gn::size_type n) {
  Gn ret(n);
  ret.insert(Pn_identity(n));
  return ret;
}
Gn gen_cycle(Pn g0) {
  Gn ret(g0.get_n());
  Pn g = Pn_identity(g0.get_n());
  while (true) {
    auto test = ret.eles.insert(g);
    if (!test.second)
      break;
    g = g * g0;
  }
  return ret;
}
bool operator < (const Gn &a, const Gn &b) {
  assert(a.n == b.n);
  if (a.eles.size() != b.eles.size())
    return a.eles.size() < b.eles.size();
  for (auto i = a.begin(), j = b.begin();
      i != a.end() && j != b.end(); ++i, ++j) {
    if (!(*i == *j)) {
      return *i < *j;
    }
  }
  return false;
}
bool operator == (const Gn &a, const Gn &b) {
  assert(a.n == b.n);
  if (a.eles.size() != b.eles.size())
    return false;
  for (auto i = a.begin(), j = b.begin();
      i != a.end() && j != b.end(); ++i, ++j) {
    if (!(*i == *j)) {
      return false;
    }
  }
  return true;
}
Gn operator * (const Gn &a, const Gn &b) {
  assert(a.n == b.n);
  Gn ret(a.n);
  ret.insert(a);
  ret.insert(b);
  while (true) {
    Gn lst = ret, now(a.n);
    for (const auto &x : ret)
      for (const auto &y : ret)
        now.insert(x * y);
    ret = now;
    if (ret == lst)
      break;
  }
  return ret;
}
std::ostream& operator << (std::ostream &os, const Gn &x) {
  for (const auto &v : x)
    os << v << ", ";
  return os;
}

/*
 * Generate all of the subgroups of size n.
 */
class SubSn {
public:
  using size_type = Pn::size_type;
  using iterator = std::set<Gn>::iterator;
  using const_iterator = std::set<Gn>::const_iterator;
  SubSn(size_type n);
  size_type gen_n() const { return n; }
  iterator begin() { return subs.begin(); }
  const_iterator begin() const { return subs.begin(); }
  iterator end() { return subs.end(); }
  const_iterator end() const { return subs.end(); }
private:
  std::set<Gn> subs;
  size_type n = 0;
  
  friend std::ostream& operator << (std::ostream &os, const SubSn &x);
};

void SubSn_gen(const std::set<Gn>::iterator beg,
    const std::set<Gn>::iterator end,
    std::set<Gn> &subs, Gn now) {
  for (auto it = beg; it != end; ++it) {
    auto nxt = now * *it;
    auto nxtbg = it; ++nxtbg;
    subs.insert(nxt);
    SubSn_gen(nxtbg, end, subs, nxt);
  }
}
SubSn::SubSn(size_type n) : n(n) {
  Gn all = gen_all(n);
  std::set<Gn> set_initial;
  for (const auto &v : all)
    set_initial.insert(gen_cycle(v));
  Gn identity_group = gen_id(n);
  subs.insert(identity_group);
  SubSn_gen(set_initial.begin(), set_initial.end(), subs, identity_group);
}
std::ostream& operator << (std::ostream &os, const SubSn &x) {
  SubSn::size_type last_order = -1;
  for (const auto &v : x) {
    if (v.get_size() != last_order) {
      os << "Order " << v.get_size() << ":\n";
      last_order = v.get_size();
    }
    os << "{" << v << "}\n";
  }
  return os;
}
int main() {
  SubSn S(4);
  std::cout << S;
  return 0;
}

The output (needs ~30s) is

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Order 1:
{(1), }
Order 2:
{(1), (34), }
{(1), (23), }
{(1), (24), }
{(1), (12), }
{(1), (12)(34), }
{(1), (13), }
{(1), (13)(24), }
{(1), (14), }
{(1), (14)(23), }
Order 3:
{(1), (234), (243), }
{(1), (123), (132), }
{(1), (124), (142), }
{(1), (134), (143), }
Order 4:
{(1), (34), (12), (12)(34), }
{(1), (23), (14), (14)(23), }
{(1), (24), (13), (13)(24), }
{(1), (12)(34), (13)(24), (14)(23), }
{(1), (12)(34), (1324), (1423), }
{(1), (1234), (13)(24), (1432), }
{(1), (1243), (1342), (14)(23), }
Order 6:
{(1), (34), (23), (234), (243), (24), }
{(1), (34), (13), (134), (143), (14), }
{(1), (23), (12), (123), (132), (13), }
{(1), (24), (12), (124), (142), (14), }
Order 8:
{(1), (34), (12), (12)(34), (13)(24), (1324), (1423), (14)(23), }
{(1), (23), (12)(34), (1243), (1342), (13)(24), (14), (14)(23), }
{(1), (24), (12)(34), (1234), (13), (13)(24), (1432), (14)(23), }
Order 12:
{(1), (234), (243), (12)(34), (123), (124), (132), (134), (13)(24), (142), (143), (14)(23), }
Order 24:
{(1), (34), (23), (234), (243), (24), (12), (12)(34), (123), (1234), (1243), (124), (132), (1342), (13), (134), (13)(24), (1324), (1432), (142), (143), (14), (1423), (14)(23), }