1
$\begingroup$

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

  • For size 2, $E = 1$, and the one number is given by $0^1 1^1 = 01$.

  • For size 4, $E = 2$, and the two numbers are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

  • For size 8, $E = 3$, and the three numbers are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

  • For size $n = 2^E$, the $E$ numbers include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ numbers can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Is there an algorithm using bit manipulation that can generate each of these numbers in the set with algorithm in the range of $O(1)$ to $O(n)$?

Important Note: I am looking for an algorithm that generates binary numbers not strings unless transformation from strings to binary numbers can be in the range of $O(1)$ to $O(n)$.

$\endgroup$
4
  • 1
    $\begingroup$ The desired pattern wasn't clear to me from the examples. I generally don't find examples to be a good substitute for a clear, general specification of the problem. As such, I'm not sure what problem you're trying to solve or what you are asking. $\endgroup$
    – D.W.
    Mar 4 '21 at 2:13
  • $\begingroup$ This requires a family of regexes. $\endgroup$ Mar 4 '21 at 4:45
  • $\begingroup$ @D.W We can create a sequence of sets. For size 2 strings we have 0^1 1^1. For size 4 strings we have (0^1 1^1)^1 or 0^2 1^2. For size n strings we have (0^k 1^k)^(n-k) $\endgroup$ Mar 4 '21 at 4:48
  • $\begingroup$ @D.W. The question has been updated more $\endgroup$
    – helluvaq
    Mar 5 '21 at 0:11
0
$\begingroup$

Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

  • For size 2, $E = 1$, and the one string is given by $0^1 1^1 = 01$.

  • For size 4, $E = 2$, and the two strings are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

  • For size 8, $E = 3$, and the three strings are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

  • For size $n = 2^E$, the $E$ strings include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ strings can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Thus, the examples are:

  • Size 2: $E = 1$. The one string is $(0^1 1^1)^1 = (0^{2^0}1^{2^0})^{2^0}$

  • Size 4: $E = 2$. The two strings are $0101 = (0^1 1^1)^2 = (0^{2^0} 1^{2^0})^{2^1}$ and $0011 = (0^2 1^2)^1 = (0^{2^1} = 1^{2^1})^{2^0}$.

  • Size 8: $E = 3$. The three strings are $01010101 = (0^{2^0} 1^{2^0})^{2^2}$ with $k = 0$, $00110011 = (0^{2^1} 1^{2^1})^{2^1}$ with $k = 1$, $00001111 = (0^{2^2} 1^{2^2})^{2^0}$ with $k = 2$.

This is an iterative algorithm. You list each string, of length $n$ a total of $\log n$ times. It is $O(n \log n)$ to list all the strings explicity. It is $O(\log n)$ to express them regex style like $(0^x 1^x)^y$ [note $x, y$ are powers of 2, and the exponents in the power form of $x, y$ add up to $E-1$].

$\endgroup$
2
  • $\begingroup$ Thanks for explaining the question better. Questions: 1. How is it 𝑂(log𝑛) to generate each of the strings? 2. Is there any pseudo generation algorithm for this using bit manipulation? 3. In case of generation of all possible combinations with iteration, shouldn't the time complexity be 𝑂(log𝑛*log𝑛) if expressing each of them is 𝑂(log𝑛)? $\endgroup$
    – helluvaq
    Mar 4 '21 at 18:59
  • $\begingroup$ Good catch. I assume if the exponents are comst lengtb. $\endgroup$ Mar 4 '21 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.