Amidakuji (Japanese: 阿弥陀籤) is a method for producing a random permutation of a set of objects.
In the beginning, a number of parallel vertical lines are drawn, one for each object. Then a specified number of horizontal rungs are added, each lower than any previous rungs. Each rung is drawn as a line segment spanning a randomly select pair of adjacent vertical lines.
For example, the following diagram depicts an Amidakuji with three objects (
The coloured lines in the diagram illustrate how to form the permutation. For each object, starting from the top of its vertical line, trace downwards but follow any rung encountered along the way, and record which vertical we end up on. In this example, the resulting permutation happens to be the identity:
Let
You are also given that
Find
阿弥陀签(亦称为画鬼脚)是为一组物体产生一个随机排列的方法。
开始时,我们绘制一组相互平行的竖直线,每个物体都对应一条竖直线。然后我们绘制若干水平线段来连接某一组相邻的竖直线。每一条水平线段都要严格低于其上方的线段。
例如,下面这张图描述了一张阿弥陀签。这张阿弥陀签共有三条分别代表物体
上图中,红、绿、蓝色的线条阐释了产生排列的方法:对于某个物体,我们从代表它的那条竖直线的顶端开始沿绘制的线下行。一旦遇到横线,就沿横线方向继续行进。最终记录下我们最终所处的那条竖直线。在此例中,最终产生的排列碰巧就是原排列:
记
求
点 这个链接 回到源站。
点 这个链接 回到详细版题目目录。