CODEWITHSUNDEEP
algorithmbinary
Amay Singh
Amay Singh

Reputation: 21

The algorithm to generate binary numbers from 1 to n in lexicographical order

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

Upvotes: 2

Views: 632

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59253

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

  1. The first symbol that changes must increase (otherwise you'll get an earlier symbol)
  2. The first symbols that changes must be as far right as possible (otherwise there would be a smaller lexicographical change); and
  3. 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:

  1. If you can append a zero without exceeding n, then do so;
  2. 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 2x-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 2x-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.

Upvotes: 1

user1196549
user1196549

Reputation:

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

Upvotes: 1

Abhinav Mathur
Abhinav Mathur

Reputation: 8111

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

Upvotes: 2

Related Questions