1 2 3

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-循环置换。如果一个变换将 i1 $\rightarrow$ i2, i2 $\rightarrow$ i3, $\ldots $ ik $\rightarrow $ i1, 而其他各元不变,那么该置换称为k-循环置换(k-cycle),写作 ( i1,i2,i3 $\ldots $ ik ).

除了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

不知道为什么PO上来就歪了