当前位置：文江博客话题详情

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

发布于 2025-01-14 01:15:17 字数 116 浏览 0 评论 0原文

有没有有效的算法可以做到这一点，我尝试过生成所有二进制数并将它们存储在数组中然后对它们进行排序，如果我们可以直接按字典顺序生成二进制数，代码会快得多。例如：n=7 产生 1,10,100,101,11,110,111

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

燃情 2025-01-21 01:15:17

这里的关键属性是，0 始终位于 1 之前，因此您可以使用递归来解决这个问题。该算法如下所示：

则从1开始递归
如果当前数字>，。 n，忽略它
否则，将其添加到输出列表中。调用 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))

The key property here is, 0 will always come before 1, so you can use recursion to solve this. The algorithm would look like:

Start recursion from 1
If current number > n, ignore it
Else, add it to the output list. Call recursion(curr_number + "0") and recursion(curr_number + "1")

This is a simple algorithm, which can be easily implemented in most languages.

Edit: Python implementation:

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))

回复收藏 0 原文

墨离汐 2025-01-21 01:15:17

如果将完整二叉树逐行编号，从 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 来获得二进制表示形式。）

If you number a complete binary tree row by row, from 1 to 2^d-1, the enumeration of the nodes in lexicographical order is the preorder traversal. Now as the two children of a node carry the value of the parent followed by 0 or by 1, we have the recursive enumeration

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)

(You can also obtain the binary representations by concatenating 0's or 1's as you go.)

回复收藏 0 原文

故事未完 2025-01-21 01:15:17

您可以遵循一些规则来生成任何字符串集的字典顺序中的下一个项目：

第一个更改的符号必须增加（否则您将得到更早的符号）
第一个更改的符号必须尽可能位于最右侧尽可能（否则词典变化会较小）；第一次更改后的符号
必须尽可能小（否则会再次出现较小的词典变化）。

对于对二进制字符串进行排序，这些规则很容易应用。在每次迭代中：

如果您可以在不超过 n 的情况下追加一个零，那么就这样做；
否则，找到最右边可能的 0，将其更改为 1，并删除余数。在这种情况下，“最右边可能的 0”是产生 <= n 的结果的最右边的 0。如果 n 不是 2^x-1，这不一定是最右边的。

使用按位运算符可以很容易地实现这种迭代，从而产生了这种很好的快速算法。为了简化步骤 (2)，我们假设 n 为 2^x-1，然后检查我们的输出：

def printLexTo(n):
    val=1
    while True:
        if val<=n:
            print("{0:b}".format(val))
        if 2*val <= n:
            val *= 2
        else:
            # get the smallest 0 bit
            bit = (val+1) & ~val
            # set it to 1 and remove the remainder
            val = (val+1)//bit
            if val==1:
                # there weren't any 0 bits in the string
                break

在线尝试

通常情况下，这种迭代算法比递归算法快得多，但提出它需要对解决方案的结构有更深入的了解。

There are a few rules you can follow to generate the next item in a lexicographical ordering of any set of strings:

The first symbol that changes must increase (otherwise you'll get an earlier symbol)
The first symbols that changes must be as far right as possible (otherwise there would be a smaller lexicographical change); and
The symbols after the first change must be made as small as possible (otherwise again there would be a smaller lexicographical change).

For ordering the binary strings, these rules are easy to apply. In each iteration:

If you can append a zero without exceeding n, then do so;
Otherwise, find the rightmost possible 0, change it to a 1, and remove the remainder. The "rightmost possible 0" in this case is rightmost one that produces a result <= n. This is not necessarily the rightmost one if n is not 2^x-1.

This iteration is pretty easy to implement with bitwise operators, leading to this nice quick algorithm. To simplify step (2), we assume that n is 2^x-1 and just check our outputs:

def printLexTo(n):
    val=1
    while True:
        if val<=n:
            print("{0:b}".format(val))
        if 2*val <= n:
            val *= 2
        else:
            # get the smallest 0 bit
            bit = (val+1) & ~val
            # set it to 1 and remove the remainder
            val = (val+1)//bit
            if val==1:
                # there weren't any 0 bits in the string
                break

Try it online

As is often the case, this iterative algorithm is a lot faster than recursive ones, but coming up with it requires a deeper understanding of the structure of the solution.

回复收藏 0 原文

~没有更多了~