A survey on keeler's theorem and application of symmetric group for swapping game

International Conference on Science and Applied Science (Engineering and Educational Science) 2016

物理学;工业技术;教育

Pratama, Yohanssen^1 ; Prakasa, Yohenry^2

Faculty of Informatics and Electrical Engineering, Del Institute of Technology, Jl. Sisingamangaraja, Sitoluama Laguboti Toba Samosir

22381, Indonesia^1

Faculty of Mathematics and Natural Sciences, Bandung Institute of Technology, Indonesia^2

关键词: Algorithm complexity;    Symmetric groups;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/795/1/012048/pdf
DOI  :  10.1088/1742-6596/795/1/012048

来源: IOP

【 摘 要 】

An episode of Futurama features two-body mind-switching machine which will not work more than once on the same pair of bodies. The problem is "Can the switching be undone so as to restore all minds to their original bodies?" Ken Keeler found an algorithm that undoes any mind-scrambling permutation, and Lihua Huang found the refinement of it. We look on the process how the puzzle can be modeled in terms group theory and using symmetric group to solve it and find the most efficient way of it. After that we will try to build the algorithm to implement it into the computer program and see the effect of the transposition notion into the algorithm complexity. The number of steps that given by the algorithm will be different and one of algorithms will have the advantage in terms of efficiency. We compare Ken Keeler and Lihua Huang algorithms to see is there any difference if we run it in the computer program, although the complexity could be remain the same.