Make delicious recipes!

De Bruijn Sequence


Given a string (like ABCD), generate shortest String containing all combinations of the given string.

Example: For "AB", all combinations are {AA, AB, BA, BB}
One string containing all these combinations is AAABBABB.
But this is not the shortest.
Shortest string containing all combinations is AABBA
Such a string is called De Bruijn Sequence


Solution: Start with solution string containing 'n' characters, all set to the lowest character.
('n' is the length of the input string)

For the next character, choose highest character such that the string formed by the last n-1 characters of current
result and this character does not exist in the result.

If it does exist, choose the next highest character.


A java program to generate the DeBruijn Sequence is as follows:
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;

public class TextContainingAllCombinations
{
    private static String generateDeBruijnSequence (
        String s,
        Set<String> combinations
    ) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);

        // Start with all chars set to the shortest one
        String res = "";
        for (int i=0; i<s.length(); i++)
            res += chars[0];
        combinations.add(res);

        // Now check all possible combinations
        int suffixLen = s.length()-1;
        while (true)
        {
            String suffix = res.substring(res.length()-suffixLen);
            int i;
            //for (i=0; i<chars.length; i++)
            for (i=chars.length-1; i>=0; i--)
            {
                if (!combinations.contains(suffix + chars[i]))
                {
                    res = res + chars[i];
                    combinations.add(suffix + chars[i]);
                    break;
                }
            }
            
            //if (i>=chars.length)
            if (i<0)
                break;
        }
        return res;
    }

    public static void main (String args[])
    {
        String s = "ABC";
        Set<String> combinations = new LinkedHashSet<String>();
        String res = generateDeBruijnSequence(s, combinations);
        System.out.println ("Result: " + res);
        System.out.println ("Result length: " + res.length());

        System.out.println ("Combinations: ");
        for (String sub: combinations)
        {
            System.out.println (sub);
        }
        System.out.println ("No of combinations: " + combinations.size());
    }
}
Execution for "PQ"
Result: PPQQP
Result length: 5
Combinations: 
PP
PQ
QQ
QP
No of combinations: 4


Execution for "ABC"
Result: AAACCCBCCACBBCBACABCAABBBABAA
Result length: 29
Combinations:
CAB
CAC
CCA
CCB
CCC
CAA
ACC
BBA
ACB
BBC
BBB
AAA
AAC
AAB
CBA
CBB
BAC
BAA
ACA
BAB
CBC
BCC
ABC
BCB
ABB
ABA
BCA
No of combinations: 27

Order of execution: If N is the length of input string, then NN combinations are possible.
To make sure all of them are in the final output string, the outer loop will run NN times.
Also, there will be several failed comparisons on line 29 which will also be of order N.
So total order will be NN+1


Note the two commented lines on lines 26 and 37
The above algorithm works only if the next character chosen is the highest character possible.
If next lowest character is chosen, the algorithm stops very soon.

Example execution when lowest character is chosen:
Result: AAABAACAA
Result length: 9
Combinations: 
AAA
AAB
ABA
BAA
AAC
ACA
CAA
No of combinations: 7

An example use of De-Bruijn Sequence

Consider a PIN-like code lock without an "enter" key which accepts the last n digits entered.
For example, a 4-digit digital ATM lock would have 104 solutions.
The De-Bruijn sequence can be used to shorten a brute-force attack on such a lock from 4x104 sequence to 104 + 4-1 string.







Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal