This is a terminal based program to do various comparisions on permutations (defined on symmetric groups) and also to find the set of all reduced word representing a permutation. A word is basically a notation for transpositions, and we try to find the list of all words that do this with least elements possible.
To achieve this we are using a structure called tower diagrams. They represent the transpositions that are used in the word. For example:
Reverse of identity permutation in S6 = [6, 5, 4, 3, 2, 1] (in line notation)
^ (symmetric group of order 120)
[6, 5, 4, 3, 2, 1] = 545345234512345 = 5 45 345 2345 12345
^ (here, number 5 denote the transposition (5,6) and so on ..)
i.e.
[6, 5, 4, 3, 2, 1] = (5,6)(4,5)(5,6)(3,4)(4,5)(5,6)(2,3)(3,4)(4,5)(5,6)(1,2)(2,3)(3,4)(4,5)(5,6) (in cycle notation)
^ (you may check, if you do not believe me)
5 45 345 2345 12345 is one of many ways to represent [6, 5, 4, 3, 2, 1] in S6. This is one of the reduced words for reverse identity permutation. There are in total 292864 many of them, which the algorithm can easily calculate. There is a shorter example below, for the reverse of identity in S5. You are encouraged to check some of them, to see that they indeed represent [5, 4, 3, 2, 1].
All reduced words for [5, 4, 3, 2, 1] , 768 in total:
4342341234 4342314234 4342312434 4342312343 4342134234 4342132434 4342132343 4342123423 4342123243 4341234123
4341231423 4341231243 4341213423 4341213243 4324341234 4324314234 4324312434 4324312343 4324134234 4324132434
4324132343 4324123423 4324123243 4323431234 4323413234 4323412342 4323412324 4323143234 4323142342 4323142324
4323124342 4323124324 4323123432 4321434234 4321432434 4321432343 4321423423 4321423243 4321343234 4321342342
4321342324 4321324342 4321324324 4321323432 4321243423 4321243243 4321234323 4321234232 4321232432 4314234123
4314231423 4314231243 4314213423 4314213243 4312434123 4312431423 4312431243 4312413423 4312413243 4312343123
4312341323 4312341232 4312314323 4312314232 4312312432 4312143423 4312143243 4312134323 4312134232 4312132432
4234231234 4234213234 4234212342 4234212324 4234123412 4234123142 4234123124 4234121342 4234121324 4232431234
4232413234 4232412342 4232412324 4232143234 4232142342 4232142324 4232124342 4232124324 4232123432 4231423412
4231423142 4231423124 4231421342 4231421324 4231243412 4231243142 4231243124 4231241342 4231241324 4231234312
4231234132 4231231432 4231214342 4231214324 4231213432 4213423412 4213423142 4213423124 4213421342 4213421324
4213243412 4213243142 4213243124 4213241342 4213241324 4213234312 4213234132 4213231432 4213214342 4213214324
4213213432 4212342312 4212342132 4212324312 4212324132 4212321432 4134234123 4134231423 4134231243 4134213423
4134213243 4132434123 4132431423 4132431243 4132413423 4132413243 4132343123 4132341323 4132341232 4132314323
4132314232 4132312432 4132143423 4132143243 4132134323 4132134232 4132132432 4123423123 4123421323 4123421232
4123412312 4123412132 4123243123 4123241323 4123241232 4123214323 4123214232 4123212432 4123142312 4123142132
4123124312 4123124132 4123121432 4121342312 4121342132 4121324312 4121324132 4121321432 3432341234 3432314234
3432312434 3432312343 3432134234 3432132434 3432132343 3432123423 3432123243 3431234123 3431231423 3431231243
3431213423 3431213243 3423421234 3423412341 3423412314 3423412134 3423241234 3423214234 3423212434 3423212343
3423142341 3423142314 3423142134 3423124341 3423124314 3423124134 3423123431 3423123413 3423123143 3423121434
3423121343 3421342341 3421342314 3421342134 3421324341 3421324314 3421324134 3421323431 3421323413 3421323143
3421321434 3421321343 3421234231 3421234213 3421232431 3421232413 3421232143 3413234123 3413231423 3413231243
3413213423 3413213243 3412342123 3412341231 3412341213 3412324123 3412321423 3412321243 3412314231 3412314213
3412312431 3412312413 3412312143 3412134231 3412134213 3412132431 3412132413 3412132143 3243421234 3243412341
3243412314 3243412134 3243241234 3243214234 3243212434 3243212343 3243142341 3243142314 3243142134 3243124341
3243124314 3243124134 3243123431 3243123413 3243123143 3243121434 3243121343 3241342341 3241342314 3241342134
3241324341 3241324314 3241324134 3241323431 3241323413 3241323143 3241321434 3241321343 3241234231 3241234213
3241232431 3241232413 3241232143 3234321234 3234312341 3234312314 3234312134 3234132341 3234132314 3234132134
3234123421 3234123241 3234123214 3231432341 3231432314 3231432134 3231423421 3231423241 3231423214 3231243421
3231243241 3231243214 3231234321 3214342341 3214342314 3214342134 3214324341 3214324314 3214324134 3214323431
3214323413 3214323143 3214321434 3214321343 3214234231 3214234213 3214232431 3214232413 3214232143 3213432341
3213432314 3213432134 3213423421 3213423241 3213423214 3213243421 3213243241 3213243214 3213234321 3212434231
3212434213 3212432431 3212432413 3212432143 3212343231 3212343213 3212342321 3212324321 3143234123 3143231423
3143231243 3143213423 3143213243 3142342123 3142341231 3142341213 3142324123 3142321423 3142321243 3142314231
3142314213 3142312431 3142312413 3142312143 3142134231 3142134213 3142132431 3142132413 3142132143 3124342123
3124341231 3124341213 3124324123 3124321423 3124321243 3124314231 3124314213 3124312431 3124312413 3124312143
3124134231 3124134213 3124132431 3124132413 3124132143 3123432123 3123431231 3123431213 3123413231 3123413213
3123412321 3123143231 3123143213 3123142321 3123124321 3121434231 3121434213 3121432431 3121432413 3121432143
3121343231 3121343213 3121342321 3121324321 2434231234 2434213234 2434212342 2434212324 2434123412 2434123142
2434123124 2434121342 2434121324 2432431234 2432413234 2432412342 2432412324 2432143234 2432142342 2432142324
2432124342 2432124324 2432123432 2431423412 2431423142 2431423124 2431421342 2431421324 2431243412 2431243142
2431243124 2431241342 2431241324 2431234312 2431234132 2431231432 2431214342 2431214324 2431213432 2413423412
2413423142 2413423124 2413421342 2413421324 2413243412 2413243142 2413243124 2413241342 2413241324 2413234312
2413234132 2413231432 2413214342 2413214324 2413213432 2412342312 2412342132 2412324312 2412324132 2412321432
2343231234 2343213234 2343212342 2343212324 2343123412 2343123142 2343123124 2343121342 2343121324 2342321234
2342312341 2342312314 2342312134 2342132341 2342132314 2342132134 2342123421 2342123241 2342123214 2341323412
2341323142 2341323124 2341321342 2341321324 2341234212 2341234121 2341232412 2341232142 2341232124 2341231421
2341231241 2341231214 2341213421 2341213241 2341213214 2324321234 2324312341 2324312314 2324312134 2324132341
2324132314 2324132134 2324123421 2324123241 2324123214 2321432341 2321432314 2321432134 2321423421 2321423241
2321423214 2321243421 2321243241 2321243214 2321234321 2314323412 2314323142 2314323124 2314321342 2314321324
2314234212 2314234121 2314232412 2314232142 2314232124 2314231421 2314231241 2314231214 2314213421 2314213241
2314213214 2312434212 2312434121 2312432412 2312432142 2312432124 2312431421 2312431241 2312431214 2312413421
2312413241 2312413214 2312343212 2312343121 2312341321 2312314321 2312143421 2312143241 2312143214 2312134321
2143423412 2143423142 2143423124 2143421342 2143421324 2143243412 2143243142 2143243124 2143241342 2143241324
2143234312 2143234132 2143231432 2143214342 2143214324 2143213432 2142342312 2142342132 2142324312 2142324132
2142321432 2134323412 2134323142 2134323124 2134321342 2134321324 2134234212 2134234121 2134232412 2134232142
2134232124 2134231421 2134231241 2134231214 2134213421 2134213241 2134213214 2132434212 2132434121 2132432412
2132432142 2132432124 2132431421 2132431241 2132431214 2132413421 2132413241 2132413214 2132343212 2132343121
2132341321 2132314321 2132143421 2132143241 2132143214 2132134321 2124342312 2124342132 2124324312 2124324132
2124321432 2123432312 2123432132 2123423212 2123423121 2123421321 2123243212 2123243121 2123241321 2123214321
1434234123 1434231423 1434231243 1434213423 1434213243 1432434123 1432431423 1432431243 1432413423 1432413243
1432343123 1432341323 1432341232 1432314323 1432314232 1432312432 1432143423 1432143243 1432134323 1432134232
1432132432 1423423123 1423421323 1423421232 1423412312 1423412132 1423243123 1423241323 1423241232 1423214323
1423214232 1423212432 1423142312 1423142132 1423124312 1423124132 1423121432 1421342312 1421342132 1421324312
1421324132 1421321432 1343234123 1343231423 1343231243 1343213423 1343213243 1342342123 1342341231 1342341213
1342324123 1342321423 1342321243 1342314231 1342314213 1342312431 1342312413 1342312143 1342134231 1342134213
1342132431 1342132413 1342132143 1324342123 1324341231 1324341213 1324324123 1324321423 1324321243 1324314231
1324314213 1324312431 1324312413 1324312143 1324134231 1324134213 1324132431 1324132413 1324132143 1323432123
1323431231 1323431213 1323413231 1323413213 1323412321 1323143231 1323143213 1323142321 1323124321 1321434231
1321434213 1321432431 1321432413 1321432143 1321343231 1321343213 1321342321 1321324321 1243423123 1243421323
1243421232 1243412312 1243412132 1243243123 1243241323 1243241232 1243214323 1243214232 1243212432 1243142312
1243142132 1243124312 1243124132 1243121432 1241342312 1241342132 1241324312 1241324132 1241321432 1234323123
1234321323 1234321232 1234312312 1234312132 1234232123 1234231231 1234231213 1234213231 1234213213 1234212321
1234132312 1234132132 1234123212 1234123121 1234121321 1232432123 1232431231 1232431213 1232413231 1232413213
1232412321 1232143231 1232143213 1232142321 1232124321 1231432312 1231432132 1231423212 1231423121 1231421321
1231243212 1231243121 1231241321 1231214321 1214342312 1214342132 1214324312 1214324132 1214321432 1213432312
1213432132 1213423212 1213423121 1213421321 1213243212 1213243121 1213241321 1213214321
⬇️ The diagram for the word 5 45 345 2345 12345,and the one on the right is the diagram for 56789 456 3456 23 4 1.
⬇️ The diagram for the word 45 89 7 123 ,and the one on the right is the diagram for 8 7 1 9 56 1 78, which is not a reduced word.
If what you read still sound chinese to you, consider taking a look at the following articles:
-
O. Coşkun, M. Taşkın, Sorting and generating reduced words, Arch. Math. 101 (2013), 427-436
-
A. Garsia, The saga of reduced factorizations of elements of the symmetric group
- A terminal emulator of your choice
- A C/C++ compiler
- SAGE , this is optional
Compile directly from source code, and then run the executable output. Preferrably, you need to have the make utility installed on your system. In MacOS or Linux you may compile everything with the following, there is no need for root privileges:
$ make all
By default the Makefile uses GNU Project Compiler if you are using something else, what you need to do is, create object files for tower-diagram.cpp and functions.cpp. After that you need to compile the driver code reduced-word.cpp together with those two helpers. With gcc it would look like the following:
$ g++ tower-digram.cpp (by default the ouput file name is tower-diagram.o)
$ g++ functions.cpp (by default the output file name is functions.o)
$ g++ reduced-word.cpp tower-diagram.o functions.o -o output_name
$ ./output_name
There is already a Makefile to automate this process, but if you are on Windows and using MinGW or a derivative, you may need to do it manually. Many IDE's also have support for Makefile file structure, so you may also use them.
After compiling, you may clean all the outputs with make clean, and acsess the program by coming to the directory you compiled and writing ./output_name.
The make command above also compiles tower-diagram-calculate.cpp, if you compiled manually then repeat the same steps above this time for the file tower-diagram-calculate.cpp instead of reduced-word.cpp . After you run the executable output, you will be asked to provide a word. A representation of the tower will be printed to the terminal. In addition, the program will ask whether or not you'd like to store the data for the diagram in a seperate file. It will be named given_word-vertex.txt . In order to create an image out of this data, SAGE is required.
There are a couple different ways to use tower-diagram.sage script file.
- Through the SAGE interactive shell.
$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.8.beta5, Release Date: 2022-12-11 │
│ Using Python 3.8.10. Type "help()" for help. │
└────────────────────────────────────────────────────────────────────┘
sage: load("tower-diagram.sage")
.
. (the script will ask for a vertex data file, follow the prompts)
.
- You may also give
tower-diagram.sageas an argument tosage, if you are going to use the script multiple times keep in mind that this method is slower, because every time this command is called SAGE loads necessary functions, which takes some time.
$ sage tower-diagram.sage
.
. (follow the prompt)
.
- If you have
sagein yourPATH, you may also runtower-diagram.sagejust like a shell script.
For that, you should add #!/usr/bin/env sage to the beginning of tower-diagram.sage and turn it into an executable. These steps will change depending on your OS. On Linux, you would do the following:
$ sed -i '1i #!/usr/bin/env sage' tower-diagram.sage
$ chmod +x tower-diagram.sage
$ ./tower-diagram.sage
.
. (follow the prompt)
Copyright (c) 2022 cutiness
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.