1
$\begingroup$

I am looking for an efficient way of finding the smallest set of $N$-tuples containing only $0$ and $1$ such that all $N$-tuples containing only $0$ and $1$ can be generated by circularly shifting elements of this set.

Consider the case $N=2$. There are 4 tuples $(0,0)$,$(0,1)$,$(1,0)$ and $(1,1)$ but the tuple $(0,1)$ is a circularly shifted version of $(1,0)$ so this set suffices: $\{(0,0),(0,1),(1,1)\}$.

Consider the case $N=3$. There are 8 tuples $(0,0,0)$,$(0,0,1)$,$(0,1,0)$,$(0,1,1)$,$(1,0,0)$,$(1,0,1)$,$(1,1,0)$,$(1,1,1)$. This set suffices: $\{(0,0,0),(0,0,1),(0,1,1),(1,1,1)\}$, because all 8 tuples can be generated by circularly shifting elements of this set.

Clearly it is possible to generate all $2^N$ such tuples and laboriously check if they are shifted versions of an already generated tuple, giving an $O(2^{2N-1})$ algorithm.

Is there a more efficient way of generating this set of tuples?

In other words, I'm looking for an algorithm that generates the set of all $N$-tuples of binary numbers "up to translation", so to speak. This set is smaller than the set of all $N$-tuples of binary numbers (but probably still has a size that is exponential in $N$). It is not unreasonable to wonder if an algorithm faster than $O(2^N)$ might exist.

$\endgroup$
  • 1
    $\begingroup$ it is too early to accept an answer, i was beginning to think o an algorithm since you made it all clear now $\endgroup$ – Abr001am Mar 1 '16 at 12:45
1
$\begingroup$

For any $N$-tuple of binary numbers $b = (b_1,b_2,\ldots,b_n) \in \{0,1\}^N$.
Let

  • $I(b)$ be the integer $\sum_{i=1}^n b_i 2^{i-1}$.
  • $L(b) = (b_2,b_3,\ldots,b_n,b_1)$ be the $N$-tuple obtained by a left-rotate.

For each $b$, accept it as a basis when $I(b) = \min\big\{ I(L^k(b)) : 0 \le k < N \big\}$.

The complexity of this algorithm is $O(N 2^N)$. This is probably not the fastest but relatively simple to implement. The biggest advantage of it is easily parallelizable/vectorizable.

If you can afford an $O(2^N)$ memory consumption, you can reduce the time complexity to $O(2^N)$.

  • Mark all $N$-tuples not visited.
  • Loop through all $N$-tuple $b$.
    • If $b$ has not been visited before,
      • accept $b$ as basis,
      • mark all shifted versions of $b$ as visited.
$\endgroup$
  • $\begingroup$ That is better than what I thought of, but I continue to wonder if there is a way of doing it in less than $O(2^N)$ - after all, the size of the set of tuples is less than $O(2^N)$. $\endgroup$ – Wouter Mar 1 '16 at 11:14

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.