R包排列：用于操作有限集合的软件工具（2020）

软件X 11（2020）100453原始软件出版物介绍PermutationsR包Robin K.S. 汉金奥克兰理工大学，Wellesley Street，Auckland，New Zealandar t i cl e i nf o文章历史记录：收到2019年收到修订版，2020年2月13日接受，2020年关键词：排列凯莱a b st ra ct在这里，我介绍R包排列，用于操作有限集合的排列。我展示了如何包已被用来调查的megaminx难题，并展示了一个82转的超级翻转，代表了一个新的下限为这个操作。©2020作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本1.0-4用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2019_202Code Ocean compute capsule NAGPL许可证使用git的代码版本控制系统软件代码语言、工具和服务使用R编译要求、操作环境R如果有开发人员文档/手册链接https://cran.r-project.org/web/packages/permutations/permutations.pdf电子邮件至hankin. gmail.com软件元数据当前软件版本1.0-4此版本可执行文件的永久链接https://github.com/RobinHankin/permutations法律软件许可证GPL计算平台/操作系统类Unix、Linux、OS X、Windows安装要求和依赖关系R如果可用，链接到开发人员文档/手册https://cran.r-project.org/web/packages/permutations/permutations.pdf问题支持电子邮件hankin. gmail.com1. 动机和意义有限集合的排列是数学的一个重要而有趣的分支，与组合学[1]，群论[2]和娱乐数学的各种分支[3]有联系;统计应用包括秩数据的建模[4]。一个有限集合的排列集合，连同一个二元算子电子邮件地址：hankin. gmail.com。https://doi.org/10.1016/j.softx.2020.100453表示函数的合成，形成n个元素上的对称群。置换的研究是群论研究的基础：凯莱R编程语言[5]是一个统计计算环境，具有广泛的数学和计算学科的功能。在这里，我将介绍permutations包，一套以R为中心的功能2352-7110/©2020作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx−→（）下一页={个FF·（）下一页·=·=3=2R.K.S. Hankin / SoftwareX 11（2020）100453它允许人们使用自然的R语言来研究计算群论。该软件包可用于任何实体重新排列，但特别适用于考虑“扭曲的难题”，如魔方和megaminx。这种扭曲的难题是娱乐数学的一个重要而有趣的分支，是许多未解决问题的主题，其中之一是在这里考虑的。permutations包实现的许多思想都用于freegroup和Stokes软件包[6，7]。1.1. 现有工作有一些计算群论R语言。请注意，有许多R包实现了“置换测试”的不相关概念例如，1.2. 有限集我们考虑来自集合[n] 1，2，3，.的双射。. .，n为自身。举一个具体的例子，取下图定义的f：[9]123456789926354178它以单词形式指定f。因此f（1）9，f（2）2和如果我们想确定f（f（f（）F （），则更方便的是用循环形式表示f，其中置换被分解成不相交的循环，通常写在圆括号中。在这里，f=（1987）（ 364）> f^3[1]（1789）> 逆（f）{1}{2} {3} {4} {5} {6} {7} {8}{9}[1]7 .第一 次会议。四六。3891（单词形式中的点表示所讨论的元素映射到其自身）。给定另一个这样的循环g=（142），那么我们可以用两种方式组合f和g，其中fg=（19872364）和gf=（12643987）。在R中：>G<- 作为循环（c（1，4，2））> f* g{1}{2} {3} {4} {5} {6} {7} {8}{9}[1] 9163.2478> g *f{1}{2} {3} {4} {5} {6} {7} {8}{9}[1] 三九六二。4178该软件包允许用户以循环形式打印所有排列，这在许多情况下都是首选：> 选项（print_word_as_cycle= TRUE）> f* g[1]（19874362）> g *f[1]（13642987）>(note只有打印方法发生了变化;内部代表，对象的表示不变）。 的一种计量方法它是f和g的1-→ 9-→非交换性是交换子的紧凑表示，这里定义8−f→4−→7−→13-写为作为f−1g−1fg：> 换位子（f，g）对他们自己那么很明显，f3是循环（1789）：f3=（1987）（ 364）（ 1987）（ 364）（ 1987）（ 364）=（ 1789）如果我们想反转函数f（），那么使用word形式更方便，交换两行，并对顶行进行排序1234567897246538912. 软件描述置换包提供了在R会话中执行置换操作正如我们所看到的，有些操作更容易以单词形式执行，有些则以循环形式执行;形式之间的转换是可能的，但计算代价很高，并且包可以存储任何一种形式的排列上面的习惯用法是：> library（“permutations”）> （f-as.word（c（9，2，6，3，5，4，1，7，8）{1}{2} {3} {4} {5} {6} {7} {8}{9}[1]9.第九条。63.4178> 第50集9.1The Lostof theWorld（1987）FF[1]（14239）>包是矢量化的。假设我们希望考虑一个二十面体的对称群[11]，已知它同构于一组五个元素的偶排列群> S5<- allperms（5）> (A5- S5[是偶数（S5）]）[1]（）（345）（354）（23）（45）（234）（235）（243）[8]（245）（24）（35）（253）（254）（25）（34）（12）（45）（12）（34）[15]（12）（35）（123）（12345）（12354）（12453）（124）（12435）[22]（12543）（125）（12534）（132）（13452）（13542）（13）（45）[29]（134）（135）（13）（24）（13245）（13524）（十三）（二十五）（13254）[36]（13425）（14532）（143）（145）（14）（35）[43]（14523）（十四）（二十三）（14235）（14253）（14325）（十四）（二十五）（15432）[50]（152）（15342）（153）（154）（15）（34）（15423）（15）（23）[57]（15234）（15243）（15324）（15）（24）其中函数perms（）取自partitionspackage [12]。因此，S5是所有大小为5的排列，而A5只是偶数排列。我们可以考虑向量A5的前四个元素，并结合长度为9的循环> A5[1：4] * shift_cycle（9）[1]（123456789）（123546789）（1236789）（1246789）作为最后一个例子，我们可以用另一个元素计算上面前四个偶数排列的共轭11x和y的共轭，记作xy，定义为y−1xy;该记法的动机是xz yz=（xy）z和xyx=（xy）z。R.K.S. Hankin/SoftwareX 11（2020）1004533Fig. 1. 大美女> A5[1：4]^as.word（7：1）[1]（）（354）（345）（34）（56）> data（“megaminx”）> 五魔方白色该软件包包括用于分析排列的功能，例如排列的形状（即，不相交循环的长度集）：> （p-rperm（3，9））[1]（142398675）（17862）（35）（49）（123）（47965）> 形状（p）[[1]][1]9[[第2期][1]5 2 2[[3]][1]3 5我们可以证明共轭不会改变置换的形状（即不相交循环的长度集）：> 相同（形状（p），形状（p^as.word（1：4）[1]真正2.1. 数据输入该软件包包括从数据创建置换对象的多种方法。虽然提供了诸如shift_cycle（）之类的低级函数，但char2cycle（）是矢量化的，并包含了许多语法，以免迫使用户记住语法：> char2cycle（c（“（1，4）（6，7）"，"（8，3，19）"，“（8319）"，"（）”）[1]（1，4）（6，7）（3，19，8）（1，9，8，3）（）其他用户友好的函数包括permutations（），它试图自动检测其参数的格式并适当地行为。3. 典型例子：Megaminxmegaminx是一个十二面体的拼图，其结构类似于魔方[13];见图。1.一、排列包可以用来操作megaminx，给每个面分配一个1-129的数字（见图1）。2）并使用随包提供的megaminx（10，12，14，16，18）（11，13，15，17，19）（21，33，45，57，69）... (23，35，47，59，61）紫（15，67，91，81，35）（16，68，92，82，36）（17，69，93，83，37）...(21，23，25，27，29）暗黄（17，29，89，79，47）（18，20，80，70，48）（19，21，81，71，49）......(31，33，35，37，39）...橙色（27，99，121，71，37）（28，90，122，72，38）（81，83，85，87，89）对象megaminx是一个12元素（已命名）的置换向量，元素对应于每个面顺时针旋转72°在实践中，使用缩写名称更容易脸转过来（“W”表示白色，“Pu "表示紫色，以此> （W^2*Pu^2*DY^2）^8白（10，46）（14，60）（16，22）（20，36）（24，68）（28，82）（32，48）（38，80）这表明这种操纵具有特别吝啬的效果。3.1. 超级翻转一个特别令人愉快的模式上的megaminx是超级翻转，显示在图。1（b）.在这种模式中，每个边缘片是在正确的位置，但翻转。在魔方上有一个相当有理论意义的等价物[14]：它是已知的第一个需要20步的配置[15]。一个具有挑战性的任务是在最少的转弯次数内完成超级翻转。克拉克[16]认为，转折数的下限是24，并提供了一个83圈的序列，在目前的符号是：> X<- W/Pu * W* Pu^2/DY^2> Y<- LG^（-1）/ DB* LB* DG> Z<- Gy^（-2）* LB/ LG/Pi/ LY> superflip 83-（X^6）^Y+Z^9# superflip（杰里米·克拉克）（使用了包习惯用法;注意使用二进制直觉上很清楚，超级翻转超越了任何操作序列，因此处于megaminx组的中心。计算群论软件，如GAP [8]可以用来证明megaminx中心只包括超翻转和单位元。超级翻转位于中心可以直接验证> random_minx-permprod（sample（megaminx，30，replace=TRUE））> isTRUE（random_minx*superflip83== superflip83*random_minx）[1]真正4R.K.S. Hankin / SoftwareX 11（2020）100453图二. 十 二 面体网络的两种着色，显示小平面编号方案;在每个五边形面中，小平面编号由中心大数的十倍给出，单位由小数字给出。因此，左上方的刻面是数字41，右下方的刻面是105。向左，开始;向右，转动白脸一按。3.2. 一个82转的超级空翻图3.第三章。 与图 2，但顺序不同。左，100个随机旋转;右，超级空翻。翻转所有30条边，但详尽的计算机搜索显示，这是不可能的。克拉克排列包可以用来搜索系统自动为一个超级空翻与更少的动作比克拉克的83圈，我在这里证明，一个轻微的改进是可能的。克拉克人们可能会认为，可以将18边翻转器和12边翻转器连接起来，这里表示为Y，其以翻转所有30个边的方式对准小平面;不存在具有三圈共轭器的这种类型的超翻转。然而，我们可以继续使用以下观察结果。首先，我们看到纯鳍状肢是megaminx群的正规子群，因为它们是自逆的，并且在合成下是闭的;因此，将纯鳍状肢与任何序列共轭给出+=-=关于我们R.K.S. Hankin/SoftwareX 11（2020）1004535一个纯翻转器（也就是说，如果X是纯的，那么y−1Xy也是纯的）。此外，给定两个纯翻转A a1。. . a n和B b1。. . bm，交织序列a1. . . a rb1. . . b m a r1. . . N也是纯的。因此，我们寻求一个形式为L6的纯12边、30圈翻转器和另一个形式为M9的纯18边、45圈翻转器，以及一个三圈共轭器abc，使得c −1 b −1 a −1 l 1. . .l rm 1 。 . .m 45 l r+1 。 . .l 30 abc（1）是一个纯粹的30边超翻转，对于某个r，1r30。这一过程将导致长度为2.3045 2 2182圈，翻转偶数个边。一个广泛并且正在进行的计算机搜索通过所有可能的组合揭示了确实存在翻转30个边的这种类型的序列，即超级翻转。下面展示了一个这样的82转超级翻转：> 超级翻转82-+ LB^-1 * Gy^-1 * LB^-1 * O^3 * Gy * LY^2 * Gy^2 *+ LY^3 * Gy^3 * LY^3/LB * Gy^2 *+（（Pu^-1 *W^2* DY* DB* R）^9）^（O^3 * LB^3/LG）*+ Gy^2/LB * O^3 * Gy * LY^2 * Gy^2 * LY^3 * Gy^3 *+ LY^3/ LB/ Gy/ LB *+ 0^3 * Gy * LY^2 * Gy^2 * LY^3 * Gy^3 * LY^3> isTRUE（superflip82 == superflip83）[1]真正用现有的方法来改进这个结果似乎并不容易（见图2）。 3）。4. 影响和结论置换包提供了一套方便有效的以R为中心的例程，便于研究群论应用，如megaminx。研究人员可以很容易地在R环境中探索计算群论的新途径。该软件包被用来寻找一个82转的超级翻转，这是该操作的一个新的下限进一步的工作可能包括从计算的角度利用R语言的统计功能来研究统计群论[17]竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1]斯坦利RP。枚举组合学，第一卷。剑桥大学出版社;2011.[2]米尔恩JS群论（v3.13）2013年，见www.jmilne.org/math/。[3]阿弗巴赫B，陈O.通过娱乐数学解决问题。Dover;2000.[4]Hankin RKS. Hyper 2包的部分秩数据：广义Bradley-Terry模型的似然函数。R J 2017;9（2）：429[5]R核心团队R：统计计算的语言和环境。奥地利维也纳：R Foundation forStatistical Computing; 2019，https：www.R-project.org/。[6] Hankin RKS. 自 由 团 体 ： 自 由 团 体 。 2019 年 ， R 包 版 本 1.1-2 。https://github.com/RobinHankin/freegroup.git网站。[7] Hankin RKS. 斯 托 克 斯 ： 外 部 演 算 。 2019 年 ， R 包 版 本 1.0-3 。https://github.com/RobinHankin/stokes.git网站。[8]GAP集团。GAP4.10.2. 2019年，https://www.gap-system.org。[9]Meurer A，Smith CP，Paprocki M，Čertík O，Kirpichev SB，Rocklin M，Kumar A，Ivanov S，Moore JK，Singh S，Rathnayake T，Vig S，GrangerBE，Muller RP，Bonazzi F，Gupta H，Vats S，Johansson F，Pedregosa F，Curry MJ，Terrel AR，Roučka v，Saboo A，Fernando I，Kulal S，CimrmanR，Scopatz A. Sympy：Python中的符号计算。PeerJ Comput Sci 2017;3. e103。http://dx.doi.org/10.7717/peerj-cs.103网站。[10]辛普森GL。permute：用于生成数据的受限排列的函数。2019年，R包版本0.9-5。https://CRAN.R-project.org/package=permute.[11]小米勒W.对称群及其应用。中国科学院出版社，1972年.[12]Hankin RKS. R中的可加整数分拆。2006年《统计软件》杂志;代码片段16.[13]乔伊纳·D群论中的冒险北京：北京出版社，2008.[14]罗基基湾在四分之一转的度量中，魔方的数字接近上帝。大学数学J2014;45（4）：242-53.[15]里德·M超唇需要20次面部旋转。1995年，http://cube20.org/cubelovers/CL15/002.txt。[16]Clark J. TwistyPuzzles.com topic - Megaminx Superflip. 2012年，twistypuzzles.com/~sandy/forum/viewtopic.php? f=8& t=24479。[17]Erdös P，Turán P.关于统计群理论的一些问题- I。ZWahrscheinlichkeitstheorVerwandte1965;4：175-86.