熄灯算法 - 找到打开所有开关的最少开关数

Question

这组开关位于水平行中。最右边的开关可以随时打开或关闭。任何其他开关只有在其右侧的开关打开且右侧的所有其他开关都关闭时才能切换。所有开关最初都是关闭的。创建一个函数，它接受 n 个开关和 returns 打开所有开关所需的最小开关次数。切换开关的每一步都需要输出。

Example: 
n = 3;
[0; 0; 0] --> [0; 0; 1] --> [0; 1; 1] --> [0; 1; 0] --> [1; 1; 0] --> [1; 1; 1];
count = 5.

我的想法是测试我们要启用的下一个开关。然后检查其右侧的每个开关并检查所需的状态。您可以建议什么解决方案？

Answer 1

这实际上产生了一个 Gray code 序列。

虽然你当然可以用一种非常天真的方式来实现它，但我们也可以使用以下观察：当我们从右到左对数组中的索引进行编号时，从最右边的条目为 0，然后数字应切换的索引遵循以下顺序：

0 1 0 2 0 1 0 3 0 1 0 2 0...

当我们从1开始对输出进行编号时，上述索引对应于该编号中最右边1位的索引。这个 table 应该可以说明这一点：

output numbering	in binary	index of rightmost 1	Gray code
1	00001	0	00001
2	00010	1	00011
3	00011	0	00010
4	00100	2	00110
5	00101	0	00111
6	00110	1	00101
7	00111	0	00100
8	01000	3	01100
9	01001	0	01101
10	01010	1	01111
...

如果输入不超过 31（灯泡），我们可以使用 32 位操作来导出最右边 1 位的索引。例如 i & ~(i - 1) returns 设置的 i 的最低有效位——作为 2 的幂。要将 2 的幂转换为位索引，我们可以使用鲜为人知的 Math.clz32函数。

我们可以跟踪有多少灯泡点亮并在所有点亮时停止循环（实际上无需在每次迭代中从零开始计算灯泡）：

function steps(bulbCount) {
    let i, onCount;
    const bulbs = Array(bulbCount).fill(0);
    console.log(...bulbs);
    
    for (i = 1, onCount = 0; onCount < bulbCount; i++) {
        let index = bulbCount + Math.clz32(i & ~(i - 1)) - 32;
        bulbs[index] ^= 1; // Toggle
        onCount += bulbs[index] || -1; // Either increment or decrement
        console.log(...bulbs);
    }

    return i - 1; // Number of switch actions
}

console.log("Number of switch operations: ", steps(4));

对于更多的灯泡，您需要用相同原理的更“手动”实现来替换位运算符，但是当您必须等待超过 2 个时几乎没有任何实际用途³¹ 个要生成的输出...

备选

我们还可以使用来自 Wikipedia 的以下观察结果：

the ^th Gray code is obtained by computing ⊕ ⌊/2⌋

虽然此计算使用 32 位运算符很简单，但需要在每次迭代中根据数字构建数组：

function steps(bulbCount) {
    let i, onCount,
        bits = 0,
        end = (1 << bulbCount) - 1;
    const bulbs = Array(bulbCount).fill(0);
    console.log(...bulbs);
    for (i = 1; bits < end; i++) {
        bits = i ^ (i >> 1);
        console.log(...Array.from(bits.toString(2).padStart(bulbCount, "0"), Number));
    }

    return i - 1; // Number of switch actions
}

console.log("Number of switch operations: ", steps(4));

熄灯算法 - 找到打开所有开关的最少开关数

Lights Out Algorithm - FInd the minimum number of switches to turn on all switches

javascript

algorithm

bit-manipulation

备选