CODEWITHSUNDEEP
arraysalgorithmbinarybit-manipulationpermutation
TTho Einthausend
TTho Einthausend

Reputation: 608

How to generate a Bitsequence with certain properties

I want to generate a Bitsequence of minimal length, where at last one 0 stands between 2 1, given a positive integer x.

Examples:

0 is x=0

1 is x=1

00 is x=2

01 is x=3

10 is x=4

000 is x=5

001 is x=6

010 is x=7

100 is x=8

101 is x=9

0000 is x=10

Etc.

Exists there Building scheme which creates these Bitsequences from the given integer x?

Upvotes: 1

Views: 113

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

If you just want to generate the sequence, we can do it by appending zeros or ones appropriately.

JavaScript code:

function f(n){
  let result = [['']]
  while (n >= 0){
    let next = []
    for (s of result[result.length-1]){
      if (n-- >= 0)
        next.push(s + 0)
      if ((!s || s[s.length-1] == '0') && n-- >= 0)
        next.push(s + 1)
    }
    result.push(next)
  }
  return result.slice(1)
}

console.log(JSON.stringify(f(10)))

Upvotes: 0

zw324
zw324

Reputation: 27190

Observe the number of encodings N(n) with length n and starts with 0 or 1 are:

n 0 1 total

1 1 1 2

2 2 1 3

3 3 2 5

4 5 3 8

These columns are actually shifted fibonacci sequences, since for a n digit sequence, if it starts with 1 then the next digit cannot be 1, so we only have N(n-2) choices, but if it starts with 0 then we have N(n-1) choices.

Using this, you can convert the original problem into "finding the k-th encoding of length l" by computing the length of the encoding and how many encodings have a smaller length. This transformed problem can be solved by recursion. There are only O(logn) digits, so this will end within O(logn).

Python code:

# 10-32
# 0000
# 0001
# 0010
# 0100
# 0101
# 1000
# 1001
# 1010
# 00000
# 00001
# 00010
# 00100
# 00101
# 01000
# 01001
# 01010
# 10000
# 10001
# 10010
# 10100
# 10101
# 000000
# 000001

fib = [1, 1, 2, 3, 5, 8, 13, 21]

def encode(m):
    d = 1
    for i in fib[2:]:
        if m < i:
            break
        m -= i
        d += 1
    s = ''
    for i in range(d, 0, -1):
        if m < fib[i]:
            s += '0'
        else:
            m -= fib[i]
            s += '1'
    return s

for i in range(50):
    print(i, encode(i))

Upvotes: 3

Related Questions