完美洗牌：隐藏在简单算法中的奇异分形

发布: 3天前 (2025年12月11日 GMT+8 02:57)

6 min read

原文: Dev.to

Source: Dev.to

引言

我一直对能够产生复杂图案的基础算法着迷。其中一种算法是 完美洗牌（在扑克牌魔术师中称为 Faro 洗牌）。在对实体扑克牌进行实验后，我转向编程，以探索其异常特性并生成惊人的分形。

完美洗牌算法

完美洗牌以一种极其简单的方式重新排列数组中的元素：

将数组分成两等份。
将第一半的元素放入偶数位置，将第二半的元素放入奇数位置。

JavaScript 实现（内洗）

function shuffle(array) {
    const half = array.length / 2;
    const temparray = [];
    for (let i = 0; i

为简化起见，我们只关注内洗，并假设数组长度为偶数（奇数长度的数组会让最后一个元素保持不变）。

周期性

由于该算法是确定性的且可能状态的数量是有限的，反复洗牌最终会把数组恢复到原始顺序。所需的迭代次数始终 ≤ 数组长度。

数组长度	返回所需迭代次数
12	12
14	4

长度为 2n 的数组的迭代计数序列在 OEIS 中被编为 A002326。下面的 JavaScript 代码用于计算它：

function a002326(n) {
    let a = 1, m = 0;
    do {
        a = (a * 2) % (2 * n + 1);
        m++;
    } while (a > 1);
    return m;
}
for (let n = 1; n < 11; n++) {
    console.log(a002326(n));
}

逆转属性

对于某些长度，数组在特定的迭代次数后会出现顺序逆转。例如：12 元素的数组在第 6 次迭代时逆转。

可视化洗牌

状态空间图

X 轴：元素数量（除以 2）
Y 轴：返回起始状态所需的迭代次数

这些点呈现出混沌分布的特征。

二进制模式可视化

将数组的前半部分填充为 0（黑），后半部分填充为 1（白）。每一行代表数组的一个状态；行按连续迭代堆叠。示例：

142–150 元素的数组
288 元素（144 × 2）
610 元素

仓库中的小脚本（shuffle1d.html）可以生成这些图案。输入半尺寸并点击 Draw。

跟踪单个元素

元素在每次迭代后的位置信息可以直接计算：

x[n+1] = {
    x[n]/2 + y/2, if x[n] is even;
    (x[n] - 1)/2, if x[n] is odd;
}

其中 y 为数组长度。长度为 2–22 的绘图显示出不可预测的轨迹。将许多此类轨迹堆叠会产生类分形图像（原文中可点击查看）。

扩展到矩阵

简单矩阵技巧

在每次迭代时反转第二半部分元素的顺序。
翻转（交换）第二半部分的元素。

这些操作在对矩阵进行洗牌时非常有用。

行列洗牌

function shufflecr(array) {
    const half = array.length / 2;
    const temparray = [];

    for (let x = 0; x < half; x++) {
        temparray[x * 2] = [];
        temparray[x * 2 + 1] = [];
        for (let y = 0; y < half; y++) {
            temparray[x * 2][y * 2] = array[x + half][y + half];
            temparray[x * 2 + 1][y * 2] = array[x][y + half];
            temparray[x * 2][y * 2 + 1] = array[x + half][y];
            temparray[x * 2 + 1][y * 2 + 1] = array[x][y];
        }
    }
    return temparray;
}

该函数同时洗牌行和列。对 80 × 80 矩阵使用它会产生错综复杂的图案；再加入第二条对角线会产生莫尔条纹效果。更大的矩阵（例如 242 × 242）在第 27–35 次迭代时会展现出演化结构。

类环面行为

当矩阵被视为环面（边缘相连）时，边缘效应在仅几次迭代后即可显现。

从洗牌生成分形

Morse–Thue 序列

通过迭代扩展数组并与其反转副本进行洗牌，可得到 Morse–Thue 序列（OEIS A010060）：

[1,0]
→ [1,0,0,1]
→ [0,1,1,0]
→ [0,1,1,0,1,0,0,1]
→ …

该二进制序列是经典的分形。

基于矩阵的分形

复制矩阵。
应用变换（旋转、翻转）。
将原矩阵与变换后的副本进行洗牌。

可能的变换（编号 0‑15）：

0：保持不变
1‑7：旋转（0°、90°、180°、270° 等）
8‑15：翻转（镜像）

反复使用类似 0, 0, 7, 7 的模式（其中动作 7 表示顺时针旋转 90°）会在若干迭代后产生独特的分形。若省略完美洗牌而使用相同的动作，则会得到另一种有趣的图案。

其它视觉技巧

叠加一份带有透明白像素的矩阵副本，并将其旋转 90°。
在叠加之前对副本进行垂直旋转。

这些技巧进一步丰富了使用完美洗牌能够实现的视觉复杂度。

所有代码片段均提供了语法高亮提示。OEIS 序列 A002326 与 A010060 的链接已保留供参考。