De Bruijn sequence
==========

Is it possible to arrange :math:`2^n` digits of 0 and 1 around a circle such that considering all consecutive intervals of length :math:`n`, they generate all :math:`n`-bit binary numbers?

Conversion to Hamiltonian Cycle
------------------

Our first idea for modeling this problem is as follows:

We construct a graph with :math:`2^n` vertices where each vertex corresponds to an :math:`n`-length binary string. There is a directed edge from vertex :math:`a` to vertex :math:`b` if by removing the last digit of string :math:`a` and adding one digit to its beginning, we obtain string :math:`b`. Now the problem becomes equivalent to finding a Hamiltonian cycle in this graph!

Here we reach an impasse, as we have no general method to determine whether a graph contains a Hamiltonian cycle.

Conversion to Eulerian Tour
-----------------

We construct a graph with :math:`2^{n-1}` vertices where each vertex corresponds to an :math:`(n-1)`-length binary string. Each vertex :math:`u` has exactly two outgoing edges. The edge labeled 0 connects to vertex :math:`w` such that if we remove the last digit of string :math:`u` and prepend 0, the resulting string equals :math:`w`. The edge labeled 1 is defined similarly.

The key difference from the previous graph is that in the first approach, each :math:`n`-length interval on the circle corresponded to a vertex, while here it corresponds to an edge. This transforms the problem into finding an Eulerian tour in the graph. (It can be proven that since each vertex has out-degree 2, in-degree 2, and the underlying graph is connected, the graph is Eulerian).

Now if you find an Eulerian tour in the graph and write the edge labels sequentially around the circle, you will obtain our desired arrangement!

.. figure:: /_static/dot/De_Bruijn_Graph.svg
 :width: 40%
 :align: center
 :alt: اگه اینترنت یارو آشغال باشه این میاد