如何有效枚举长度为 N
的位向量这样不会同时设置两个相邻的位,仅使用位操作(不是递归)?你可以假设 N <= 64
.
“高效”是指复杂度(远)小于 O(N * 2^N)
,因为天真的方法需要 O(N * 2^N)
(即枚举所有位向量,然后删除那些与条件相矛盾的位向量)。
例如,当N = 4
, 我想要
0000
1000
1010
等等
但不是
1100
(0th和1st都设置了)0110
(第一和第二都设置好了)1111
(一切就绪)等等
This Japanese book说有这样的方式,但根本没有解释,所以我只是发布这个问题。
最佳答案
如 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
的斐二进制数(证明:根据斐二进制数的定义是微不足道的)。
关于algorithm - 枚举位向量使得不会同时设置两个相邻位的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/74784020/