# Finding all n-tuples that are not shifted versions of each other

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.

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

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.
• 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)$. – Wouter Mar 1 '16 at 11:14