通讯技术>> Finite-Group-Explorer>> 返回
项目作者： bolner

项目描述 ：
Heuristic search algorithms for abelian and non-abelian small groups for educational purposes.
高级语言： C++
项目地址: git://github.com/bolner/Finite-Group-Explorer.git
创建时间： 2020-06-07T13:17:04Z
项目社区：https://github.com/bolner/Finite-Group-Explorer
开源协议：Apache License 2.0
下载


Finite Group Explorer

Heuristic search algorithms for abelian and non-abelian small groups.

My main motivation was the lack of similar heuristic programs on the internet. I was curious which are the biggest
groups that can be found this way, and how soon would one reach a combinatorial explosion on current CPUs. (This limit seems to be around order 10 for random search and 16-20 for the systematic.)

Modules

The underlying representation of the groups in each module is done by using Cayley tables. In addition to the Cayley table, the search algorithms are making use of bitmasks that summarize values appearing on a given row or column (etc.). This technique is used frequently in Chess engines.

Module Description
LatinHeuristics.hpp Searches for reduced latin squares and disregards the associative rule#Definition). Its findings might be either quasigroups or groups when associativity appears by chance.
AssocHeuristics.hpp Searches for proper groups by using the associative rule too. The results can be both abelian and non-abelian.
RandomHeuristics.hpp Same as AssocHeuristics but the search is randomized. This has much worse performance.
CycleGraph.hpp Can generate the Graphviz and the CsAcademy code of the Cycle Graph) of a group. Can also list the cyclic subgroups of the group.
Classifier.hpp Checks for properties of the group. Now supports: Associative, Abelian, Cyclic, Simple, Dedekind, Hamiltonian. Can list the subgroups and normal subgroups.

1. Example result: A4

A4 non-abelian, alternating group, order 12.

1.1. Cycle graph

Alt text

1.2. Cayley table

* 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 3 4 5 6 7 8 9 10 11 12
2 2 1 4 3 6 5 8 7 10 9 12 11
3 3 4 1 2 7 8 5 6 11 12 9 10
4 4 3 2 1 8 7 6 5 12 11 10 9
5 5 7 8 6 9 11 12 10 1 3 4 2
6 6 8 7 5 10 12 11 9 2 4 3 1
7 7 5 6 8 11 9 10 12 3 1 2 4
8 8 6 5 7 12 10 9 11 4 2 1 3
9 9 12 10 11 1 4 2 3 5 8 6 7
10 10 11 9 12 2 3 1 4 6 7 5 8
11 11 10 12 9 3 2 4 1 7 6 8 5
12 12 9 11 10 4 1 3 2 8 5 7 6

2. Example result: G166

Abelian, order 16, product. Z4 x Z22

2.1. Cycle graph

Alt text

2.2. Generated Graphviz code of the graph

  1. strict graph Group {
  2.     node [shape=circle, fontsize=6, fixedsize=true, width=0.2]
  3.     1 [style=filled]
  5.     1 -- 9 -- 3 -- 11 -- 1
  6.     1 -- 10 -- 3 -- 12 -- 1
  7.     1 -- 13 -- 3 -- 15 -- 1
  8.     1 -- 14 -- 3 -- 16 -- 1
  9.     1 -- 2 -- 1
  10.     1 -- 4 -- 1
  11.     1 -- 5 -- 1
  12.     1 -- 6 -- 1
  13.     1 -- 7 -- 1
  14.     1 -- 8 -- 1
  15. }

2.3. Cayley table
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15
3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14
4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13
5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12
6 5 8 7 2 1 4 3 14 13 16 15 10 9 12 11
7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10
8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9
9 10 11 12 13 14 15 16 3 4 1 2 7 8 5 6
10 9 12 11 14 13 16 15 4 3 2 1 8 7 6 5
11 12 9 10 15 16 13 14 1 2 3 4 5 6 7 8
12 11 10 9 16 15 14 13 2 1 4 3 6 5 8 7
13 14 15 16 9 10 11 12 7 8 5 6 3 4 1 2
14 13 16 15 10 9 12 11 8 7 6 5 4 3 2 1
15 16 13 14 11 12 9 10 5 6 7 8 1 2 3 4
16 15 14 13 12 11 10 9 6 5 8 7 2 1 4 3

3. Example result: Dih4

Dih4: non-abelian, dihedral group, order 8, extraspecial group, nilpotent.

3.1. Cycle graph

Alt text

3.2. Generated Graphviz code of the graph

  1. strict graph Group {
  2.     node [shape=circle, fontsize=6, fixedsize=true, width=0.2]
  3.     1 [style=filled]
  5.     1 -- 2 -- 1
  6.     1 -- 3 -- 6 -- 7 -- 1
  7.     1 -- 4 -- 1
  8.     1 -- 5 -- 1
  9.     1 -- 7 -- 6 -- 3 -- 1
  10.     1 -- 8 -- 1
  11. }

3.3. Cayley table
1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 8 6 2 4 7 1 5
4 7 5 1 3 8 2 6
5 6 8 7 1 2 4 3
6 5 7 8 2 1 3 4
7 4 1 5 8 3 6 2
8 3 2 6 7 4 5 1

4. Example result: G24

Abelian, order 24. This was found by accident, when I forgot to stop a program and it ran for around an hour.

4.1. Cycle graph

Alt text

4.2. Generated Graphviz code of the graph

  1. strict graph Group {
  2.     node [shape=circle, fontsize=6, fixedsize=true, width=0.2]
  3.     1 [style=filled]
  5.     1 -- 10 -- 17 -- 2 -- 9 -- 18 -- 1
  6.     1 -- 11 -- 17 -- 3 -- 9 -- 19 -- 1
  7.     1 -- 12 -- 17 -- 4 -- 9 -- 20 -- 1
  8.     1 -- 13 -- 17 -- 5 -- 9 -- 21 -- 1
  9.     1 -- 14 -- 17 -- 6 -- 9 -- 22 -- 1
  10.     1 -- 15 -- 17 -- 7 -- 9 -- 23 -- 1
  11.     1 -- 16 -- 17 -- 8 -- 9 -- 24 -- 1
  12. }

4.3. Cayley table
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23
3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18 23 24 21 22
4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13 20 19 18 17 24 23 22 21
5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12 21 22 23 24 17 18 19 20
6 5 8 7 2 1 4 3 14 13 16 15 10 9 12 11 22 21 24 23 18 17 20 19
7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10 23 24 21 22 19 20 17 18
8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 24 23 22 21 20 19 18 17
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8
10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 2 1 4 3 6 5 8 7
11 12 9 10 15 16 13 14 19 20 17 18 23 24 21 22 3 4 1 2 7 8 5 6
12 11 10 9 16 15 14 13 20 19 18 17 24 23 22 21 4 3 2 1 8 7 6 5
13 14 15 16 9 10 11 12 21 22 23 24 17 18 19 20 5 6 7 8 1 2 3 4
14 13 16 15 10 9 12 11 22 21 24 23 18 17 20 19 6 5 8 7 2 1 4 3
15 16 13 14 11 12 9 10 23 24 21 22 19 20 17 18 7 8 5 6 3 4 1 2
16 15 14 13 12 11 10 9 24 23 22 21 20 19 18 17 8 7 6 5 4 3 2 1
17 18 19 20 21 22 23 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
18 17 20 19 22 21 24 23 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15
19 20 17 18 23 24 21 22 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14
20 19 18 17 24 23 22 21 4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13
21 22 23 24 17 18 19 20 5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12
22 21 24 23 18 17 20 19 6 5 8 7 2 1 4 3 14 13 16 15 10 9 12 11
23 24 21 22 19 20 17 18 7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10
24 23 22 21 20 19 18 17 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9

TODO

  • Add more tests into the classifier.
  • Find a decent graph rendering tool.