Math in CS:置换的轮换分解

目录 数学, 算法

随便一本《近世代数》或者《抽象代数》书上在讲到置换群的时候,应该都会讲到这样一个定理:
任何一个置换都可以表示为不相交轮换的乘积,若不计因子的顺序,其分解式是唯一的。

一、简单解释

没有数学背景的人,这句话很难读懂,下面我们来看一个简单的例子。假设我们有这样一个置换 P:

1, 2, 3, 4, 5
2, 5, 4, 3, 1

那么这个置换是什么样的轮换的乘积呢?我们先从 1 出发,1 被换到 2,2 被换到 5,5 又被换到 1,这就是一个轮换;然后再从 3 出发,3 被换到 4,4 又被换到 3,这又是一个轮换。也就是说 P 是两个不相交轮换 (1, 2, 5) 和 (3,4) 的乘积。

二、一个应用:全排列判断问题

下面我们来看这个定理有什么作用,考虑下面这道题目[1][2]:

给一个 n 长的数组,判断它是否为一个 1, 2, ..., n 的全排列,要求在线性时间,常数空间内实现。

我们可以容易看到,每个全排列都可以视为 1, 2, ..., n 上的一个置换。问题就转化为检测该数组是不是一个 1, 2, ..., n 的置换。由本文开头提到的定理可知,我们只需要检查该置换是不是由不相交的轮换构成的即可。

还是上面那个例子,怎么检查

1, 2, 3, 4, 5
2, 5, 4, 3, 1

是不是一个置换呢?首先从 1 开始,a[1]=2,那么再检查 a[a[1]]=a[2]=5,然后再检查a[a[a[1]]]=a[5]=1,这样就发现了一个轮换 (1, 2, 5)。然后接下来检测第二个,第三个轮换...

如何保证检查的高效以及所有轮换都不相交呢?我们每次检查完一个数,就将它置负,这样遇到负值,循环就终止了。如果终止前检查的那个数与起始的数相同,那么我们就发现了一个轮换,否则它就不是一个轮换,说明 P 不是一个置换。由于检查过的轮换中的数字都被置为负值,所以第二个轮换肯定不会与第一个轮换相交。如果到最后所有的数都被置为负值,且循环正常终止,那么说明它们都在不相交的轮换里,那么 P 就是一个置换。

如果想要查找过程不影响最终数组的值,到最后把所有置负的元素都重新置正即可。

代码实现如下[2]:

/* We use a n+1 elements array a[n+1] for convenience. a[0] is used to store
 * the return value, thus is not part of the permutation.  */
int test_perm(int *a, int n)
{
  int i, j;
  if (a == NULL)  return 0;     /* Test input */
  a[0] = 1;
  for (i = 1; i <= n; ++i)      /* Test input */
    if (a[i] < 1 || a[i] > n) { /* Is a[i] in the range 1~n? */
      a[0] = 0;
      return a[0];
    }

  for (i = 1; i <= n; ++i)
    if (a[i] > 0) {
      j = i;
      while (a[j] > 0) {        /* Follow the cycle */
        a[j] = -a[j];
        j = -a[j];
      }
      if (j != i)  a[0] = 0;    /* Test the cycle */
    }

  for (i = 1; i <= n; ++i)
    a[i] = a[i] > 0 ? a[i] : -a[i];

  return a[0];
}

三、另一个应用:100 囚徒碰运气问题

那么这个定理还有其它的用处没有呢?考虑下面这道题目[3][4]:

100 个囚犯,每人有一个从 1 到 100 的不重复不遗漏的号码,国王把这些号码收集起来,打乱放进 100 个箱子里,每个箱子里有且仅有一个号码。囚犯们一个一个地来到 100 个箱子面前,每人可以打开至多 50 个箱子来寻找自己的号码,可以一个一个打开(即可以根据之前箱子里看到的号码来决定后面要打开的箱子)。如果有一个囚犯没有找到自己的号码,那么这 100 个人一起被处死;只有当所有的囚犯都找到了自己的号码,他们才会被国王全部释放。

囚犯们可以在没开箱子前商量对策,但是一但打开了箱子,他就不能告诉别人箱子和号码的对应关系。问他们应该用什么样的策略以保证最大的存活概率?

显然,每个人随机选 50 个箱子打开,100 个人的存活概率会是 1/2 的 100 次方,即1/1267650600228229401496703205376,可以小到忽略不计。但是事实上有一种极简单的办法,其存活概率高达 30% 。至于有没有更好的办法?我不知道。

存活率达 30% 的策略就是:

囚犯打开自己号码对应的箱子,就按照箱子中的号码打开另一个箱子,一直到找到自己号码或者选50 次为止,这样就能保证整体有 30% 的存活概率。

这个策略背后的数学原理是什么呢?其实国王所作的事情,就是一个 1 到 100 元素集合的置换,囚犯所做的事情,就是顺着自己号码所在的轮换找自己号码。那么什么时候所有人都不用死呢?就是这个置换中所有的轮换长度都不大于 50,因为每个囚犯号码的轮换都不大于 50,那么他总能在 50 次以内找到自己的号码。

怎么计算这个概率 P 呢?{这个置换中所有的轮换长度都不大于 50 的概率},就是 1 - {存在轮换长度大于 50 的概率},进而 1 - {存在轮换长度为 51, 52, ..., 100 的概率},由此,我们可以得到下面的等式:

P=1-\frac{1}{100!}\sum_{k=51}^{100}\binom{100}{k}(k-1)!(100-k)!=1-\sum_{k=51}^{100}%20\frac{1}{k}=1-(H_{100}-H_{50})

其中,Hn 代表调和数(Harmonic Number)。虽然调和数没有精确的公式,但是我们知道调和数和自然对数有着密切的联系[5],那么我们就可以用自然对数来近似:

P\approx1-(ln(100)-ln(50))=1-ln(2)\approx0.30685281944005469059[6]

因此,我们可以得到,使用这种策略 100个囚犯的存活概率 P 约为 30%。

[1] http://yueweitang.org/bbs/topic/22
[2] http://fayaa.com/tiku/view/84/
[3] http://tydsh.spaces.live.com/Blog/cns!435F1A315756AD5D!833.entry
[4] http://fayaa.com/tiku/view/141/
[5] http://en.wikipedia.org/wiki/Harmonic_number#Calculation
[6] 求和得到的更精确的结果是:0.31182782068980479698,Bash 代码:

STR="1-("
for i in `seq 51 99`; do
  STR+="1/$i+"
done
STR+="1/100)"
echo $STR | bc -l

用 Vim 对矩阵转置

目录 开源, 数学

前两天某个同学在科苑星空 BBS 上问到了一个有趣的问题:如何在 Vim 中对矩阵进行转置?

我当时想,转置不就是行列互换嘛,awk 可以取一列,那么拿出来每列然后打印成一行不就好了?类似于:

echo `awk '{printf "%s ",$1}' file`
echo `awk '{printf "%s ",$2}' file`
echo `awk '{printf "%s ",$3}' file`
...

本来觉得用 bash 写一个循环语句就可以了,但是怎么也尝试不出来如何替换那个 $1, $2, $3...就想没办法了只能搞 eval 了。但是我觉得这种事情 Unix 前辈们应该干过,所以就搜了一斧子,果然搜到了一个 AWK 程序,《Sed & Awk》 Ch13.9 Perform a Matrix Transposition:

#! /bin/sh
# Transpose a matrix: assumes all lines have same number of fields

exec awk '
NR == 1 {
    n = NF
    for (i = 1; i <= NF; i++)
        row[i] = $i
    next
}
{
    if (NF > n)
        n = NF
    for (i = 1; i <= NF; i++)
        row[i] = row[i] " " $i
}
END {
    for (i = 1; i <= n; i++)
        print row[i]
}' ${1+"$@"}

哈,除了觉得这样内存占用可能比较大之外,这可是一个相当不错的程序。

在 Vim 中调用就很简单了,将上面脚本保存成 transpose,加上可执行属性放在某个可执行路径下(比如 ~/bin),然后在 Vim 编辑矩阵文件时 :%!transpose 就可以了。

PS: 另外,在查证矩阵的“转置”应该写成“转秩”还是“转置”时,我在 Wikipedia 发现一个很有意思的东西:

矩阵用词
在中国大陆,横向称为“行”,纵向称为“列”。 在台湾,横向称为“列”,纵向称为“行”。

天那,要是用汉语和台湾同学讨论矩阵的话,该有多痛苦呀!

维度:数学漫步

目录 数学, 电影和音乐

开放数学电影《维度:数学漫步》(Dimensions: a walk through mathematics)是一部两小时长的 CG 科普电影,共分 9 个章节,讲述了许多深奥的数学知识,如 4 维空间中的正多胞体、复数、分形(fractals)、纤维化理论(fibrations)等等。这部电影以创作共用 署名-非商业用途-禁止演绎 3.0许可证发布,你可以自由下载和复制但不允许修改或商业使用。————援引 Solidot

这部电影我已经下载下来好长时间了,今天才想起来看一点儿,发现有点儿意思。请看这部电影开篇的话:

My name is Hipparchus. I lived in the second century before the birth of Christ, and I don't think I'd be bragging if I told you that I am the father of the sciences of Geography and Astronomy. You know, I wrote more than 14 books but unfortunately they have almost all been lost in the mists of time. I was responsible for the first catalogue of the stars, founded the field of mathematics called trigonometry and even invented the astrolabe. Fortunately, my brilliant successor Ptolemy, three centuries after my time inspired by my work, took up where I left off, and nowadays historians sometimes can't determine what was my contribution and what was his.

我叫喜帕恰斯,生活在耶稣诞生两个世纪之前。如果我说我是地理与天文学之父,请不要觉得我很狂妄。你知道的,我至少写了 14 本书。但不幸的是,它们几乎都遗失了,我曾为星星编写了第一本目录,开创了数学中的三角学,还发明了星盘。不过幸运的是,我杰出的后继者托勒密,三个世纪以后在我的工作启发之下,接手了我剩下的活计。如今,史学家们都无法确定,究竟哪些是我的贡献,哪些是他的。

这不是一部常规意义上的电影,而是用数码图形手段制作的动画。里面并没有什么主人公,制作者通过动画图形来阐述对数学维度的理解。这个电影的网站是:http://www.dimensions-math.org/,网站上提供有下载链接。另外,中国科学院数学研究所的 FTP 也提供该影片英语和法语版本的下载,详情请点击:http://www.math.ac.cn/Dimensions.htm

关于播放

有很多人在播放这部电影时候遇到问题,暴风影音是没办法播放这部电影的,Windows 媒体播放器可以播放但无法加载字幕。这里我推荐两款非常优秀的开源播放器,SMplayerVLC,它们都有 Linux 和 Windows 版本。他们都能播放这部电影,但是由于本片中文字幕使用 UTF-8 编码,字幕加载可能有一些小问题。下面是使这两款播放器能够正常显示本片中文字幕的设置(它们的菜单项在 Windows 下和 Linux 下几乎没有任何不同)。

SMplayer:
Options->Subtitles->Default subtitle encoding: UTF-8
如果是 Windows 系统,可能还需要在 Options->Subtitles->Font 中选择一下系统字体。

VLC Player:
Settings->Preferences->Video->Subtitles/OSD->Text renderer->Font:
Linux(Ubuntu) 下找到:/usr/share/fonts/truetype/wqy/wqy-zenhei.ttf(可以换成系统中其它的中文字体)
Windows 下找到:C:\WINDOWS\Fonts\simsun.ttc
Settings->Preferences->Input/Codecs->Other codecs->Subtitles->Subtitles text encoding: UTF-8

PS: 特别推荐一下 SMplayer

我在 Linux 下和 Windows 下现在都是使用 SMplayer 播放器(不用提醒我它和 mplayer 关系)。除了它的界面在两个系统下保持一致,完美支持 GBK 编码字幕之外,在播放上还有几个好处让我觉得特别顺手(可以说是我原来用暴风影音时候梦寐以求的特性):

一,支持三种速度的快进,分别用左右,上下方向键,上下翻页键。这样想跳过序幕时很方便;
二,支持以行为单位上下翻动字幕,当字幕快了慢了只需要按两个键就能调整过来;
三,自动纪录最后播放位置,再打开时自动跳到上次播放中止处;
四,normalize声音很方便,当视频声音太小时,normalize一下就舒服多了。不是其它播放器没这个功能,只是太难找到,比如暴风用这个功能要过几层菜单。