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

25 马问题

目录 算法

这是以前在 TopLanguage 讨论组讨论过的一道题目 ,题目描述为:

有 25 匹马和 1 个赛场,但赛场只有 5 条赛道,即一次只能给最多 5 匹马提供比赛机会,并且不能计时。请问如何设计比赛策略得到最快的 3/5 匹马,使得使用赛道的次数最少。

我想了一下,下面尝试给出我的分析,如果不对的话,还请指正。

一、决出前三名的策略

决出前 3 名网上有很多讨论,答案是 7 次,没有见过更少的,策略如下:

1. 将 25 匹马分成 5 组,分别赛一轮,得出一个先后顺序,共 5 轮。
2. 将每组的头马组成一组,再赛一轮,得出一个先后顺序。这第 6 轮能确定第一名。
3. 将最快一组的二三名,第二那组的一二名,以及第三那组的第一名五匹马放在一起,再赛一轮。这第 7 轮的前两名就是最终的二三名。总共赛 7 轮。

下面是分析。不失一般性,在赛 6 次之后,我们假设这 25 匹马的序号为:

A1 A2 A3 A4 A5  // 1 <-------
B1 B2 B3 B4 B5  // 2  |     |
C1 C2 C3 C4 C5  // 3 Main   |
D1 D2 D3 D4 D5  // 4  |  Extended
E1 E2 E3 E4 E5  // 5 <--    |
--------------  //          |
A1 B1 C1 D1 E1  // 6  {A1} <-

其中主矩阵列出了 25 匹马的序号,扩展矩阵的每行是每轮比赛的结果。我们可以看到主矩阵的行有序,第一列有序,那么现在我们知道第一名是 A1。

由于已知 A1 是第一名,第二名肯定是在每轮中紧挨在 A1 后面的,因此第二名的候选集为 {A2, B1}。

它们两个占不满 5 个赛道,我们再来看第三名的候选集。第三名在每轮中只可能是挨在第一或第二名的后面,也就是说在 {A1} U {A2, B1} 的后面,那么第三名的候选集就是 {A2, A3, B1, B2, C1},正好 5 匹马(第二名的候选集肯定包含在第三名候选集中)。那么第二三名只可能在这 5 匹马中,因此我们只需要让 {A2, A3, B1, B2, C1} 这 5 匹马再比一次,得到前两名,与 {A1} 合起来就是总的前三名。这样总共的比赛次数是 7 次。

2. 决出前五名的策略

决出前 5 名,就比较复杂了,我们按照同样策略再往下思考:

{A2, A3, B1, B2, C1} 决出前两名,有几种可能呢?如果它们没有比过,可能性就是从 5 个中取 2 个后的排列数,20 种可能。但是我们前面的比赛已经得到了一些快慢信息,我们就可以发现,第 7 轮 {A2, A3, B1, B2, C1} 决出前两名只有 5 种可能情况:

A2 A3 B1       B2/C1 * // 7  {A1, A2, A3}
B1 B2 A3/C1    *     * // 7  {A1, B1, B2}
B1 C1 A2/B2    *     * // 7  {A1, B1, C1}
A2 B1 A3/B2/C1 *     * // 7  {A1, A2, B1}
B1 A2 A3/B2/C1 *     *

去掉可交换的 A2 B1,其实只有 4 种情况。我们分别来考虑这 4 种情况:

1. {A1, A2, A3}

第四名肯定是 {A1, A2, A3} 之后的马,候选集为 {A4, B1};元素不足 5,再推一下第五名,即{A1, A2, A3} U {A4, B1} 之后的马,候选集为 {A4, B1, A5, B2, C1},只有 5 匹马。就是说第四、五名可以从这五匹马中产生,那么我们只需要再比一轮,取前两名,与 {A1, A2, A3} 并起来就能得到整个的前 5 匹马。那么最少的比赛次数是 8 次。

2. {A1, B1, B2}

这种情况下,同理,第四名候选集为 {A2, B3, C1} ,第五名候选集为 {A2, A3, B3, B4, C1, C2, D1},元素多于 5 个。因此我们必须先让 {A2, B3, C1} 比赛得到第 4 名,才能将第五名候选集的元素个数减少到 5 个以内。穷举:第 8 轮 A2 第一,可以消去 {C2, D1, B4, A2};B3 第一,可以消去 {B3, A3, C2, D1};C1 第一,可以消去 {C1, A3, B4},均能保证第五名的取值集合减少到 5 以内,因此只需要再一轮,就可以得到第五名。总的比赛次数是 9 次。

3. {A1, B1, C1}

同理,第四名候选集为 {A2, B2, C2, D1},第五名候选集为{A2, A3, B2, B3, C2, C3, D1, E1}。第四名无论取哪个,都会消去四个第五名候选集中的元素,总的比赛次数仍然是 9 次。

4. {A1, A2, B1}

同理,第四名候选集为{A3, B2, C1},第五名候选集为{A3, A4, B2, B3, C1, C2, D1}。第四名无论取哪个,至少消去第五名候选集中的 3 个元素,总的比赛次数也是 9 次。

穷举结束了,现在我们可以得出结论:最坏情况下该策略决出前 5 匹马的最少比赛次数是 9 次。

三、扩展问题

我有一个问题是:这种策略下取3, 5名比赛次数一定是最少的吗?有没有数学证明?

再扩展一点儿,如果需要求前 n 名,最少需要比赛几次?

在我们的这种策略下,因为主矩阵只有 5 行,每行还是有序的,那么求下一名的候选集最多有 5 个元素。也就是说多求一名,至多需要增加一轮比赛。什么情况下可以少于一轮呢?当已经确定第 n 名的情况时,第 n+2 名的候选集元素少于 5 个,我们就可以一轮比赛确定两个名次了。

我还比较好奇的是,如果需要决出所有 25 匹马的快慢顺序,最坏情况下至少需要比赛几次?

在我们这种策略下,假设 f(n) 是第 n 名最坏情况下的最少比赛次数,我们已知 f(1) = 6, f(2) = f (3) = 7, f(4) = 8, f(5) = 9,f(n) <= (n-5)+9 = n+4。那么 f(25) = f(20)+1 <= (20-5)+9 + 1 = 25 次,其上界应该是 25。但其准确值怎么确定?穷举就太困难了。 但是如果题目要求是确定 25 个的全部顺序,我们这种策略未必是最好的。这时候这题可以看成 n 路归并排序,并且可同时比较 n 个数的优化问题。过程中有很多可优化的可能。比如我们预处理时可以对每行和每列都排一下序,能否可以得到一些额外的信息?当主矩阵(去掉已确定顺序的元素)显得不那么平衡时,用扩展矩阵中的比较信息是否可以将主矩阵平衡一下,或者消去某些行列,这样做是否有帮助?

Cygwin GCC qsort 函数错误(续)

目录 开源, 算法, 编程

上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误:我脑袋陷入了一个错误的逻辑,以为 compare 函数嘛,就是要 compare 一下,那么我用 '>' 或者 '< ' 这种比较算符就可以满足要求(潜意识里认为 > 会返回 1 或者 -1,显然是错的,上篇文章的评论者 Stephen 开始也犯了同样的直觉错误,不过他马上就醒悟过来了)。我当时脑袋里也犹豫了一下要不要处理相等的情况,后来想快排算法中没有判断相等的情况,那么我没必要加上等号。

这个错误直接导致了快排算法失效。

但是为什么在 Linux 下的 gcc 可以输出正确的排序结果呢?我想了很久,最终还是把 glibc 的代码看了一下,才发现,原来当数组规模比较小时时(数组大小小于物理内存的四分之一),glibc 的 qsort 其实不使用 quick sort(_quicksort),而是使用 merge sort(msort_with_tmp)。而且在 msort_with_tmp 中,对 compare 的处理是比较其返回值是否 <=0,这样排序的结果就是正确的了。[1]

事实上最简单的快排算法是只使用 '<' 号或者 '<='的,比如 Wikipedia 上给出的快排算法,那么我们的 compare 只返回 -1 和 0 行吗?这取决于实现,比如对快排算法的优化中有一个就是对数组中有大量相等元素情况下的优化,其中一种实现 Three-way partition, 就需要使用到三种情况:大于、小于或等于。原始的快排 partition 是将数组按照与 pivot 的比较分为两段,Three-way partition 则是将数组分为三段,中间增加一段与 pivot 值相等的子数组。C 玩具代码的实现如下:

void qsort_3way(int a[], int lo, int hi)
{
  if (hi <= lo) return;
  int lt = lo, gt = hi, i = lt;
  int v = a[lo], t;
  while (i <= gt) {
    if (a[i] < v) {
      t = a[i]; a[i] = a[lt]; a[lt] = t;
      ++i; ++lt;
    } else if (a[i] > v) {
      t = a[i]; a[i] = a[gt]; a[gt] = t;
      --gt;  
    } else i++;
  }
  qsort_3way(a, lo, lt - 1);
  qsort_3way(a, gt + 1, hi);
}

但是 '<' 和 '>' 真的都需要吗?理论上来讲,'>' 是不需要的,我们显然可以将 a[i] > v 改成 v < a[i]。这也是 C++ 里面做的,C++ 中的 sort 函数只需要类重载 '< ' 运算符。但是 C 中并没有这种约定,我们不能预设 qsort 如何拿 compare() 的返回值与 0 比较。因此让 compare() 按照 C 的约定,返回大于、小于和等于 0 的三种情况是绝对正确的而且必要的。

我了解了正确的结果怎么得来的,但是我仍然不知道错误的结果是怎么得来的。看起来 Cygwin 使用的 libc 中没有采取类似 Linux 下 gcc 的策略(比如无法取到物理内存大小?)。quick sort 算法有很多优化的技巧和实现:有的使用 '< ' 符号比较,有的在分支数组足够小时采用插入排序,有的同时使用 '<', '> 两个符号,有的随机取 pivot,有的取三点中值作为 pivot。[2] 没有看到代码和调试,很难判断 Cygwin 的 libc 使用了什么算法(当然,尝试分析不同的输入输出是可以得到规律的,比密码分析还是要简单一些)。

[1] glibc/stdlib/msort.c.
[2] Jon Bentley and M. Douglas McIlroy, "Engineering a sort function", Software - Practice and Experience, Vol. 23 (11), 1249-1265, 1993.