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());
}
}

Order of execution: If N is the length of input string, then N^{N} combinations are possible.
To make sure all of them are in the final output string, the outer loop will run N^{N} times.
Also, there will be several failed comparisons on line 29 which will also be of order N.
So total order will be N^{N+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 10^{4} solutions.
The De-Bruijn sequence can be used to shorten a brute-force attack on such a lock from 4x10^{4} sequence to 10^{4} + 4-1 string.

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