Question

Gray Code

“格雷码”。一个数列，0 到 2^n - 1 的整数各出现一次，写成二进位数字。数列头尾循环，相邻数字恰有一个位数不相同，可能是 1 变 0、0 变 1。符合条件的数列，通常有许多种。

[n = 0] 0
[n = 1] 0 1
[n = 2] 00 01 11 10
[n = 3] 000 001 011 010 110 111 101 100

N 维空间，正 N 方体，边长为 1，靠在原点上，贴齐座标轴，置于第一象限。任选一个顶点开始，沿边行走，经过每个顶点各一次，走完一圈回到起点。途经座标就是一组 Gray Code！

  011         111        011________ 111
     /|      /|            /        |   
001 / |  101/ |        001/_______  |   
   |  |_____|_|110       010______|_|110
   | 010    |              /      |     
000|________|100       000/_______|100  

Gray Code 可以推广到高维度。比方说二维的情况下，Gray Code 是一个方阵，上下左右皆循环，四方向相邻数字恰有一个位数不相同。符合条件的方阵，通常有许多种。

[n = 0] 0
[n = 1] 0 1
        1 0
[n = 2] 00 01 11 10
        01 11 10 00
        11 10 00 01
        10 00 01 11

生成 Gray Code

奇数项数字，由上一个数字，改变最低位数而得；偶数项数字，由上一个数字，改变最低位的 1 的更高位数而得。

不知如何解释的方法。

Gray Code 的应用

Tower of Hanoi 河内塔的解法顺序就是 Gray Code！

Chinese Ring Puzzle 九连环的解法顺序就是 Gray Code！

http://britton.disted.camosun.bc.ca/chinesering/ninering_sol.html

UVa 10455 11535

Permutation

前言

电脑擅于处理大量资料。处理大量资料，除了大家熟悉的排序和搜寻以外，其实还有排列和组合。

有些问题需要找到最好的排列组合方式。例如求最佳排列的问题 Travelling Salesman Problem、Scheduling Problem，例如求最佳组合的问题 Partition Problem、Knapsack Problem。

想要解决这些问题，最简单的方法就是枚举法：枚举所有可能的排列、组合，一一验证，从中找到最好的排列、组合。

排列

此处的排列是名词。排列就是交换位置。排列也是交换顺序。

例如有五笔资料　　　●★■▲◆

这是其中一种排列　　▲●◆★■
这也是其中一种排列　●★■▲◆

设定编号，变成数字，方便记载。

　　　　　　　　　　12345
例如有五笔资料　　　●★■▲◆

这是其中一种排列　　41523
这也是其中一种排列　12345

替各种排列编号

http://en.wikipedia.org/wiki/Factorial_number_system

http://en.wikipedia.org/wiki/Lehmer_code

http://stackoverflow.com/questions/1506078/

UVa 941 417 11027

枚举所有排列

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

“ Backtracking ”：递迴填入数字。可以得到字典顺序。

Combination

组合（子集合）

从一堆东西当中，挑出其中几个。可以全部都挑，也可以什麽都不挑。

组合就是挑选。组合就是剔除。无关顺序。

例如有五笔资料　　　　●★■▲◆

这是其中一种组合　　　★■◆
这和方才是同一种组合　◆★■
这是其中一种组合　　　▲
这是其中一种组合　　　●★■▲◆
这是其中一种组合　　　nothing

替各种组合编号

一个二进位数字，可以代表一个子集合。

       0       1      2     3       4
U = {lemon, orange, lime, apple, banana};

　　　　　43210
二进位数字 01010，即是子集合 {orange, apple}
二进位数字 00001，即是子集合 {lemon}
二进位数字 00000，即是子集合 { }

实作程式码时，运用资料结构“ Bitset ”或“ 整数 ”储存一种组合，可以节省空间。运用程式语言的“ Bitwise Operation ”语法，可以节省时间。

Permutation

Permutation

“排列”可以看成是一对一函数，每个数字变成另一个数字。

以下用“ 图 ”解释“排列”。“排列”画成图，每个点恰有一条出边、一条入边，必然形成许多环。一个“排列”就是许多环！

因此“排列”经常写成循环节的形式。

UVa 11071 ICPC 6899

Orbit

套用一个排列，就是各点同时走一步。

持续套用同一个排列，就是各点同时走一步、走两步、……。

每个点总是绕行于自己的环裡面。

持续套用两个不同的排列，顺序随意。相交的环，都能走到。

每个点总是漫步于自己的连通分量裡面。

持续套用多个不同的排列，以此类推。

每一块走动范围称作“轨道”。

Permutation Group

给定一个排列，我们可以找出许多排列，令每个点总是绕行于自己的环裡面，不会离开环。

例如给定一个排列，共有四个环。符合上述条件的其中一个排列是：第一个环走两步，第二个环走零步，第三个环走三步，第四个环走一步。

符合上述条件的所有的相异排列，总数量等于：每个环的长度相乘！这些排列们称为一个“排列群”。

另外，若有长度一样的环（甚至呈倍数关係），可令这些环一齐走相同步数。排列数量减少了，但是仍是一个“排列群”。

给定多个不同的排列，亦得如法炮制。我们可以找出许多排列，令每个点总是绕行于自己的连通分量裡面。符合条件的所有的相异排列，也是一个“排列群”。若有构造一样的连通分量（甚至呈倍数关係），可令这些连通分量一齐走相同步法，仍是一个“排列群”。

注意到，数学家给予“群”、“排列群”、“群作用”非常明确的定义。此处省略了许多细节。

Orbit-Stabilizer Theorem

o(x) = { g‧x | g∈G }      从 x 可走到的点们。
orbit                    （一个环、一个连通分量）

s(x) = { g∈G | g‧x = x }  让 x 走回原处的排列们。
stabilizer               （x 的环走零步，其他环走随意步）

f(g) = { x∈X | g‧x = x }  套用一个排列 g，走回原处的点们。
fixed point              （某些环所走的步数，恰等于环的长度的倍数）
                         （某些连通分量所走的步法，恰回到原处）

轨道卫星定理：一个排列群，任选一点 x，|o(x)| |s(x)|相乘，等于排列群大小、等于排列总数量。

将 x 所在的轨道（暨同步轨道们），分离出来罢了。

不动点计数定理【没有正式学术名称】

sum_all_x |s(x)| = sum_all_g |f(g)|

不动点计数定理：一个排列群，所有排列的所有不动点，共有两种计数方式。

首先观察单一轨道：

左式：第一点，分别走零一二三……步，走回原处的次数；第二点，分别走零一二三……步，走回原处的次数；……。通通加起来。

右式：所有点各走零步，走回原处的点数；所有点各走一步，走回原处的点数；……。通通加起来。

接著把单一轨道推广成多个轨道，接著把环上的步数推广成连通分量上的步法，即得証。

顺带一提，此定理即是微积分 Fubini's Theorem 的实际应用。

Orbit Counting Theorem

              |o(x)| |s(x)| =          #(g)   [orbit-stabilizer theorem]
sum_one_orbit |o(x)| |s(x)| =   |o(x)| #(g)   [repeat |o(x)| times]
|o(x)| sum_one_orbit |s(x)| =   |o(x)| #(g)   [constant]
       sum_one_orbit |s(x)| =          #(g)
       sum_all_orbit |s(x)| = #(orbit) #(g)
           sum_all_x |s(x)| = #(orbit) #(g)
           sum_all_g |f(g)| = #(orbit) #(g)   [Fubini's theorem]

           sum_all_g |f(g)|
           ―――――――――――――――― = #(orbit)
                 #(g)

轨道计数定理：一个排列群，不动点的平均值，就是轨道数量。

轨道不好算，不动点很好算，因此数学家兜出这个式子。

Pólya Counting Theorem

                               #(cycles of g)
sum_all_g |f(g)|   sum_all_g  k
―――――――――――――――― = ―――――――――――――――――――――――――― = #(orbit)
      #(g)                    #(g)

这是特殊案例。排列的对象，不是 n 个东西，而是 n^k 个东西：n 个相同元件，k 种不同颜色，每个元件涂上其中一种颜色，全部的可能性。

虽然有 n^k 个东西，但是排列规则只有排列 n 个元件，并未提及元件的颜色。

波利亚计数定理：一、仅排列 n 个元件，求得虚拟排列群。此时看清楚 n^k 个东西的排列情况，恰好是真的排列群。可以套用轨道计数定理。二、此时一个排列的不动点数量，恰好是 k 的次方，次方值是该排列的循环节数量。

证明省略。请看范例。

范例：方格著色

四个方格呈田字，每个方格是白色或黑色，总共 2^4 = 16 种。

当旋转视为相同，那麽就剩下 6 种。

我们的目标是：不比对所有田字，快速算出答案是 6 种。

旋转即排列。此例当中，旋转的基本单位是 90°。

以 90°为基础，建构虚拟的排列群，涵盖所有旋转方式：顺时针旋转 90°、180°、270°、360° = 0°。此排列群是虚拟的排列群，仅考虑 4 个方格，而非 2^4 种田字。

看清楚 2^4 种田字的排列情况，这四个排列恰好是真的排列群：以 90°做为基础，每个环走每种步数、一些同步轨道。

我们的目标是：此排列群的轨道数量，就是答案，一共 6 种。

实务上没有人像我这样把所有排列详细画出来，然后找连通分量。快速的方法是轨道计数定理、波利亚计数定理，直接列出不动点，求平均值。此例的不动点，就是旋转之后，仍旧一样的田字。

不喜欢图片的话，请见文字版本。

颜色 k=2 种                      循环节数量
旋转       排列     不动点数量  括号数量
     |       g      | |f(g)| ||  cycle  | k^cycle 
---- | -------------|--------||---------|---------
  0° | (1)(2)(3)(4) |   16   ||    4    | 2^4 = 16
 90° | (1234)       |    2   ||    1    | 2^1 = 2 
180° | (13)(24)     |    4   ||    2    | 2^2 = 4 
270° | (1432)       |    2   ||    1    | 2^1 = 2 

orbit counting theorem: (16+2+4+2)/4 = 6
Pólya counting theorem: [(2^4)+(2^1)+(2^2)+(2^1)]/4 = 6

以上就是波利亚计数定理的用途。

以下另外提供颜色数量为 1、2、3 时的不动点。读者可以从中观察波利亚定理的精神。

UVa 10601 10733 11255 11540

延伸阅读：其他定理

如果你真的很喜欢群论和数论，可以研究看看。

Lagrange's theorem：子群的大小，整除群的大小。
  Cauchy's theorem：当质数 p 整除群的大小（例如排列群），
                    那麽此群存在一个元素 g（例如一个排列），
                    使得 g^p = 1（此排列套用 p 次，每个轨道刚好走零步）。
  Cayley's theorem：随便一个群，
                    一定可以等价地变成某个对称群的子群（例如排列群）。