0
$\begingroup$

I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values).

Also, I want to rank and unrank these subset of values (in polynomial time).

I have formed this regular expression -

R = (ϵ + 1 + 11)((0 + 00)(1 + 11))*(ϵ + 0 + 00)

I want to rank the allowed values using "DFA transfer matrix" or other valid approach, such that result is achieved in polynomial time and not by brute-force.

I got an approach here -

Order in a subset

However, I still need some pointers and/or pseudo-code of converting the above regular expression to code which will do the rank / unrank.

Example -

Let K = 6 digit binary value

n = 2 (maximum 2 consecutive 1s and 0s)

000000 -> (>2 consecutive 0s OR 1s) -> exclude
000001 -> (>2 consecutive 0s OR 1s) -> exclude
000010 -> (>2 consecutive 0s OR 1s) -> exclude  
000011 -> (>2 consecutive 0s OR 1s) -> exclude  
000100 -> (>2 consecutive 0s OR 1s) -> exclude  
000101 -> (>2 consecutive 0s OR 1s) -> exclude  
000110 -> (>2 consecutive 0s OR 1s) -> exclude  
000111 -> (>2 consecutive 0s OR 1s) -> exclude  
001000 -> (>2 consecutive 0s OR 1s) -> exclude  
001001 -> (<= 2 consecutive 0s AND 1s) -> rank [1]
001010 -> (<= 2 consecutive 0s AND 1s) -> rank [2]
001011 -> (<= 2 consecutive 0s AND 1s) -> rank [3]
001100 -> (<= 2 consecutive 0s AND 1s) -> rank [4]
001101 -> (<= 2 consecutive 0s AND 1s) -> rank [5]
001110 -> (>2 consecutive 0s OR 1s) -> exclude
001111 -> (>2 consecutive 0s OR 1s) -> exclude  

010000 -> (>2 consecutive 0s OR 1s) -> exclude
010001 -> (>2 consecutive 0s OR 1s) -> exclude
010010 -> (<= 2 consecutive 0s AND 1s) -> rank [6]
010011 -> (<= 2 consecutive 0s AND 1s) -> rank [7]
010100 -> (<= 2 consecutive 0s AND 1s) -> rank [8]
010101 -> (<= 2 consecutive 0s AND 1s) -> rank [9]
010110 -> (<= 2 consecutive 0s AND 1s) -> rank [10]
010111 -> (>2 consecutive 0s OR 1s) -> exclude
011000 -> (>2 consecutive 0s OR 1s) -> exclude
011001 -> (<= 2 consecutive 0s AND 1s) -> rank [11]
011010 -> (<= 2 consecutive 0s AND 1s) -> rank [12]
011011 -> (<= 2 consecutive 0s AND 1s) -> rank [13]
011100 -> (>2 consecutive 0s OR 1s) -> exclude
011101 -> (>2 consecutive 0s OR 1s) -> exclude
011110 -> (>2 consecutive 0s OR 1s) -> exclude
011111 -> (>2 consecutive 0s OR 1s) -> exclude

100000 -> (>2 consecutive 0s OR 1s) -> exclude
100001 -> (>2 consecutive 0s OR 1s) -> exclude
100010 -> (>2 consecutive 0s OR 1s) -> exclude
100011 -> (>2 consecutive 0s OR 1s) -> exclude
100100 -> (<= 2 consecutive 0s AND 1s) -> rank [14]
100101 -> (<= 2 consecutive 0s AND 1s) -> rank [15]
100110 -> (<= 2 consecutive 0s AND 1s) -> rank [16]
100111 -> (>2 consecutive 0s OR 1s) -> exclude
101000 -> (>2 consecutive 0s OR 1s) -> exclude
101001 -> (<= 2 consecutive 0s AND 1s) -> rank [17]
101010 -> (<= 2 consecutive 0s AND 1s) -> rank [18]
101011 -> (<= 2 consecutive 0s AND 1s) -> rank [19]
101100 -> (<= 2 consecutive 0s AND 1s) -> rank [20]
101101 -> (<= 2 consecutive 0s AND 1s) -> rank [21]
101110 -> (>2 consecutive 0s OR 1s) -> exclude
101111 -> (>2 consecutive 0s OR 1s) -> exclude

110000 -> (>2 consecutive 0s OR 1s) -> exclude
110001 -> (>2 consecutive 0s OR 1s) -> exclude
110010 -> (<= 2 consecutive 0s AND 1s) -> rank [22]
110011 -> (<= 2 consecutive 0s AND 1s) -> rank [23]
110100 -> (<= 2 consecutive 0s AND 1s) -> rank [24]
110101 -> (<= 2 consecutive 0s AND 1s) -> rank [25]
110110 -> (<= 2 consecutive 0s AND 1s) -> rank [26]
110111 -> (>2 consecutive 0s OR 1s) -> exclude
111000 -> (>2 consecutive 0s OR 1s) -> exclude
111001 -> (>2 consecutive 0s OR 1s) -> exclude
111010 -> (>2 consecutive 0s OR 1s) -> exclude
111011 -> (>2 consecutive 0s OR 1s) -> exclude
111100 -> (>2 consecutive 0s OR 1s) -> exclude
111101 -> (>2 consecutive 0s OR 1s) -> exclude
111110 -> (>2 consecutive 0s OR 1s) -> exclude
111111 -> (>2 consecutive 0s OR 1s) -> exclude

Appreciate your help. Many thanks.

$\endgroup$
1

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.