ghost leg (画鬼脚)

港大CS一年级data structure的作业，模拟“画鬼脚”游戏，编码测试花了三个小时，总算可以交差。在网上搜了下，发现这个简单游戏背后有着不简单的数学原理。

1. 游戏规则

画鬼脚又称画线抽签。是几个人需要用抽签来决定事物或工作的分配时，最简便的方式。进行时只需要一个能够画线的地方或物品就足够了，人数决定了竖线的条数。

在竖线的一端分别写上参与人，将需分配的事物或工作分成与人数的同等分后分别写在另一端。然后在每两个竖线相隔的区域，每个人任意的画上横线。每个人画横线的条数一般不限，但横线间不可交叉且横线不可横跨穿过两个间隔。

从写有自己名字的竖线一端开始，向另一端前进。每当遇上横线时，则沿着横线转弯走向另一根竖线，到达竖线后继续向前最终到达另一端，而这一端所写的事物便是你所抽到的事物。

2. 数学现象

当游戏结束时总是会出现1:1的对应关系，不会有多个人对应同一物品也不会有物品没有人对应。重要的是这个性质在任意条横线情况下均成立

3. 重要性质

a) 排列性

整个游戏过程会将一串输入元素排列变为另一串顺序不同的输出元素的排列

b) 周期性

可以将游戏过程看作对输入元素的变换M，则在对输入元素重复进行有限次变换后，输出元素排列会与输入元素排列相同。即

c) 可逆性

对任意变换M，存在变换，使得M =

d) 等价性

将输入序列变为同一输出序列的变换M的个数是无无限的，它们之间是等价的。那么如何寻找最小数目横线的变换呢？可以参考：http://en.wikipedia.org/wiki/Ghost_Leg

4. 游戏过程模拟

因为添加的横线距离顶端的高度不能相同，可以用链表结构来组织数据，然后设计链表上的游戏算法，整个过程也就显得清晰简单了。C代码可以从GitHub上下载: https://github.com/jia1546/ghostleg