De Bruijn sequence C++


  • 2

    From wiki: De Bruijn sequence
    "a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring".

    The De Brujin sequence has length k^n. See the proof from the link.

    "The de Bruijn sequences can be constructed by taking a Hamiltonian path of an n-dimensional de Bruijn graph over k symbols (or equivalently, an Eulerian cycle of an (n − 1)-dimensional de Bruijn graph)."

    Use Hierholzer's Algorithm to construct the Eulerian circuit.
    I read @dietpepsi 's post about this problem.

    class Solution {
        int n, k, v;
        vector<vector<bool> > visited;
        string sequence;
    public:
        string crackSafe(int n, int k) {
            if (k == 1) return string(n, '0');
            this->n = n;
            this->k = k;
            v = 1;
            for (int i = 0; i < n -1; ++i) v *= k;
            visited.resize(v, vector<bool>(k, false));
            dfs(0);
            return sequence + sequence.substr(0, n - 1);
        }
        
        void dfs(int u) {
            for (int i = 0; i < k; ++i) {
                if (!visited[u][i]) {
                    visited[u][i] = true;
                    dfs((u * k + i) % v);
                    sequence.push_back('0' + i);
                }
            }
        }
    };
    

  • 0
    M

    @IsingModel Hi, I found it hard to understand the dfs step. Could you explain sequence.push_back('0'+i)?


  • 0

    @milu The optimal case is that in the sequence every password with length-n occurs exactly once. Such a sequence has length k^n (if the sequence is cyclic), which is also the total number of distinct password.

    Here we construct the sequence for password with length-n using all the password with length-(n-1). In the code, v equals k^(n-1) that is the number of password with length-(n-1) and also the number nodes of the graph. Every node has k indegree and k outdegree. For example, n - 1 = 3, k = 3, the node with password 002 can go to 020 021 022 and can be reached by 100, 000, 200. The number of edges is k^(n-1) * k, that is k^n. That is why the dimension of visited is k^(n-1) by k. After we traverse all the edges in the graph, the sequence is constructed.

    see this graph n = 4, k = 2

    The dfs part is to traverse all the edges in the graph by Hierholzer's Algorithm. Every node has the same indegree and outdegeree so that the graph is guaranteed to have Eulerian circuit.


  • 0
    M

    @IsingModel Thanks for your reply. However, I am still not sure I understand your dfs step. I tried to modify as follows to print some info.

            for (int i = 0; i < k; ++i) {
                if (!visited[u][i]) {
                    visited[u][i] = true;
                    dfs((u * k + i) % v);
                    sequence.push_back('0' + i);
                    cout << "vertex u: " << u << "add i: " << i << endl;
                }
            }
        }
    

    Here is the result for n=3, k=2:

    vertex u: 2, add i: 0
    vertex u: 3, add i: 0
    vertex u: 3, add i: 1
    vertex u: 1, add i: 1
    vertex u: 2, add i: 1
    vertex u: 1, add i: 0
    vertex u: 0, add i: 1
    vertex u: 0, add i: 0
    

    I assumed for n=3, k=2 we'd label the vertices as:

    u=0 ------ 00
    u=1 ------ 01
    u=2 ------ 10
    u=3 ------ 11
    

    and the grap looks like:(0_1514207852446_unnamed.jpg
    Then from the printing info, it constructs the sequence by following inverse directions of edges. Is it supposed to be this way?


  • 0
    M

    @IsingModel Never mind. Now I see the inverse of a De Bruijn sequence is also a De Bruijn sequence..


  • 0

    @milu I did not reverse the sequence to have the Eulerian circuit because the sequence is cyclic.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.