Python 解置换群问题

室友问我一个问题，把我难住了。

想不出解法，遂写了个程序暴力求解。

**题目：**A permutation is applied to the string SUPERBGOLDHAT. The same permutation is applied to the output from this operation. The second output is OGTHLEPDSUARB. What was the first output? (Note: as an example, the permutation(1 3 4) applied to WOLF gives FOWL. Write your answer in capital letters inside quotation marks, e.g. “BEARDPLUGHOST”.)

把它译成中文就是：已知将某个置换作用于字符串SUPERBGOLDHAT两次，生成字符串OGTHLEPDSUARB. 求该置换作用于字符串SUPERBGOLDHAT一次时，生成的结果。

Note: 作用两次的意思就是，当一个置换规则作用于字符串一次时，会生成一个新字符串。将这个规则作用在这个新字符串上，又会生成一个字符串，这个字符串就是两次作用的结果。

近世代数基础

如果你不知道什么是置换的话，可以看一下本节。学过近世代数的同学请自觉跳过这部分ꉂ(ˊᗜˋ*)

我们给定一个序列$a ={1, 2, 3, 4, 5, 6} $ 。然后给定一个作用于该序列的置换：

$$\sigma = \left\{\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 2 & 6 & 4 & 1\end{matrix}\right\} $$

这个置换$\sigma$的作用就是，把序列$a $中的1变成3，2变成5，3变成2，4变成6，6变成1。以此类推：

第一次: 3 5 2 6 4 1

第二次: 2 4 5 1 6 3

第三次: 5 6 4 3 1 2

上述置换$\sigma$的写法叫两行式，此外，我们还可以用轮换来表示一个置换。举个例子，如下是一个两行式表示的置换。

$$\tau = \left\{\begin{matrix}1 & 3 & 4 \\ 3 & 4 & 1 \end{matrix}\right\} $$

它用轮换表示是 $\tau = (1 3 4) $ . 以上的 $\tau $ 和 $\sigma $ 都属于 k-循环置换。如果一个变换将 i₁ $\rightarrow$ i₂, i₂ $\rightarrow$ i₃, $\ldots $ i_k $\rightarrow $ i₁, 而其他各元不变，那么该置换称为k-循环置换(k-cycle)，写作 ( i₁,i₂,i₃ $\ldots $ i_k ).

除了k-循环置换之外，还有一种置换叫做非循环置换。一个k-循环置换, 总是可以表示为一个轮换。而一个非循环置换，则总是可以表示成几个轮换的积。例如，非循环置换 $ \upsilon $ 就可以表示成：

$$\upsilon = \left\{\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 2 & 3 & 5 & 1\end{matrix}\right\} = (1 6)(2 4 3)(5) = (1 6)(2 4 3) ​$$

(参考资料: 置换群题目汇总，《近世代数》杨子胥)

暴力解法

用Python暴力解轮换，没有一点暴力美学的影子。这种行为之拙计，甚至让人有一丝羞耻。那还能怎么办，谁叫俺不会手算。

下面这段代码实现了轮换操作，意图暴力求解。

import numpy as np
import itertools


# a is something like index
# b is the second output you want
# C (capital) is the first output we guess
a = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13])
a = a-1
b = np.array([8, 7, 13, 11, 9, 4, 3, 10, 1, 2, 12, 5, 6])
b = b-1
c = np.zeros([a.size])

# traverse all permutations of a
for C in itertools.permutations(a, a.size):
    print(C)
    for num in C:
		# c (lower case) is the second output in this iteration
        c[num] = C[C[num]] 
    if (b == c).all():
        C = [x+1 for x in C]
        print('The answer is ', C)
        break

这段代码大概跑了一天才跑完(巨汗)

结果如下

输出是一个数列：[6, 12, 9,10, 3, 8, 5, 4, 13, 11, 2, 7, 1]，这是什么意思呢？

要理解输出的含义，要先理解输入。输入数列a为[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]，它代表的是是原字符串 SUPERBGOLDHAT 各字母对应的数字编码，其中1代表S，2代表U，以此类推。因此输出的数字其实也是这个含义，我们只需要把输出数列中的数字，按照之前的字母与数字搭配逐个翻译，就能得到答案了。最终的解为：BALDPORETHUGS. 经过后面一节中的手算法验证，证明俺算对了！啊不，是计算机算对了。

Note1: 这段代码中，我觉得我写得最棒的一句是c[num] = C[C[num]]。之前为了实现同样的功能，至少写了十几行代码，都是血泪……后来拜读了置换群题目汇总一文，才受到启发写成这个表达形式。

Note2: 如果原问题改成已知第三次输出，求第一次输出也很容易。只要加多一层中括号就可以了c[num] = C[C[C[num]]]。哈哈哈，运气好的话你的电脑可能要跑两个星期。(๑╹っ╹๑)

手算解法

鉴于计算机实在算得太慢了，补上我新学的人脑解法 O_O