algorithm - 枚举位向量使得不会同时设置两个相邻位的有效方法

Question

如何有效枚举长度为 N 的位向量这样不会同时设置两个相邻的位，仅使用位操作(不是递归)？你可以假设 N <= 64 .

“高效”是指复杂度(远)小于 O(N * 2^N) ，因为天真的方法需要 O(N * 2^N) (即枚举所有位向量，然后删除那些与条件相矛盾的位向量)。

例如，当N = 4 , 我想要

• 0000

• 1000

• 1010

• 等等

但不是

• 1100 (0th和1st都设置了)

• 0110 (第一和第二都设置好了)

• 1111 (一切就绪)

• 等等

This Japanese book说有这样的方式，但根本没有解释，所以我只是发布这个问题。

Answer 1

如 harold's comment 中的建议, 该序列称为斐二进制数 和OEIS A003714显示了一个有效的实现。

我实现并比较了以下三种方法:

• 天真

• 递归(在 MrSmith42's comment 中建议)

• 高效算法(在OEIS中展示)

性能:

n = 32

loop:      9.726627375s
recursion: 26.339083ms
efficient: 14.795916ms

Rust 代码 ( Rust Playground ):

//naive method
fn f1(n: usize) -> Vec<usize> {
    let mut mem = Vec::with_capacity(1 << n);
    'a: for i in 0..(1 << n) {
        for j in 1..n {
            if ((i & (1 << (j - 1)) != 0) && (i & (1 << j) != 0)) {
                continue 'a;
            }
        }
        mem.push(i);
    }
    mem
}

//recursive method
fn f2(cur: usize, i: usize, n: usize, mem: &mut Vec<usize>) {
    if (i == n) {
        mem.push(cur);
        return;
    }
    if (i == 0) {
        f2(cur, i + 1, n, mem);
        f2(cur | (1 << i), i + 1, n, mem);
    } else {
        f2(cur, i + 1, n, mem);
        if (cur & (1 << (i - 1)) == 0) {
            f2(cur | (1 << i), i + 1, n, mem);
        }
    }
}

//efficient method
//The sequence is known as `Fibbinary numbers`.
//ref: |https://oeis.org/A003714|
fn f3(n: usize) -> Vec<usize> {
    let mut mem = Vec::with_capacity(1 << n);
    let mut x = 0;
    loop {
        mem.push(x);
        let y = !(x >> 1);
        x = (x - y) & y;
        if ((1 << n) & x != 0) {
            break;
        }
    }
    mem
}

use std::time::Instant;

fn main() {
    let n = 32;

    let start = Instant::now();
    let mut mem1 = f1(n);
    println!("loop:      {:?}", start.elapsed());

    let start = Instant::now();
    let mut mem2 = Vec::with_capacity(1 << n);
    f2(0, 0, n, &mut mem2);
    println!("recursion: {:?}", start.elapsed());

    let start = Instant::now();
    let mut mem3 = f3(n);
    println!("efficient: {:?}", start.elapsed());

    mem1.sort();
    mem2.sort();
    mem3.sort();
    assert_eq!(mem1, mem2);
    assert_eq!(mem1, mem3);
}

边注:

给定一个整数 x ，可以知道是否 x是 (x << 1) & x == 0 的斐二进制数(证明:根据斐二进制数的定义是微不足道的)。