Is there any efficient algorithm to do so ,I have tried to produce all binary numbers and store them in an array then sort them, if we can directly generate the binary numbers in lexicographical order the code will be much faster. For eg : n=7 produces 1,10,100,101,11,110,111

CodePudding user response：

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

1. Start recursion from 1
2. If current number > n, ignore it
3. 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))

CodePudding user response：

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