字典顺序从1到n生成二进制数的算法

Question

有什么有效的算法来做到这一点吗?我试着生成所有的二进制数字，并将它们存储在一个数组中，然后对它们进行排序，如果我们能够按照字典顺序直接生成二进制数字，代码就会快得多。例如: n=7生产1,10,100,101,11,110,111

Answer 1

这里的关键属性是，0总是在1之前，所以您可以使用递归来解决这个问题。该算法的外观如下：

1. 从1开始递归
2. 如果当前数字> n，则忽略它
3. 否则，将其添加到输出列表中。调用recursion(curr_number + "0")和recursion(curr_number + "1")

这是一个简单的算法，可以很容易地在大多数语言中实现。

编辑: Python实现：

def dfs(current_string, current_number, n):
    if current_number > n:
        return []
    strings = [current_string]
    strings.extend(dfs(current_string + "0", current_number << 1, n))
    strings.extend(dfs(current_string + "1", (current_number << 1)+1, n))
    return strings
print(dfs("1", 1, 7))

Answer 2

如果将完整的二叉树逐行编号，从1到2^d-1，则字典顺序中节点的枚举是前缀遍历。现在，由于节点的两个子节点的值后面跟着0或1，所以我们有递归枚举。

n= ...

def Emit(m):
    print(bin(m))
    if 2 * m <= n:
        Emit(2 * m)
    if 2 * m + 1 <= n:
        Emit(2 * m + 1)

Emit(1)

(您也可以通过连接0或1来获得二进制表示。)