Generating a de Bruijn sequence (in Rust)

de_bruijn.rs

fn main() {
    let args: Vec<_> = std::env::args().collect();

    if args.len() < 4 {
        eprintln!("You must enter the alphabet and the sequence size");
        return;
    }

    let alphabet = &args[2];
    let count = args[3]
        .parse::<usize>()
        .expect("count must be a positive number");

    println!("the sequence is:\n{}", de_bruijn(alphabet, count));
}

fn de_bruijn(alphabet: &String, n: usize) -> String {
    let mut a = vec![0; alphabet.len() * n];
    let mut sequence: Vec<usize> = Vec::new();

    fn db(t: usize, p: usize, k: usize, n: usize, a: &mut Vec<usize>, seq: &mut Vec<usize>) {
        if t > n {
            if n % p == 0 {
                seq.extend(&a[1..=p])
            }
        } else {
            a[t] = a[t - p];
            db(t + 1, p, k, n, a, seq);
            for j in (a[t - p] + 1)..k {
                a[t] = j;
                db(t + 1, t, k, n, a, seq)
            }
        }
    }

    db(1, 1, alphabet.len(), n, &mut a, &mut sequence);

    // Append first n-1 elements into sequence
    for i in 0..n - 1 {
        sequence.push(sequence[i].clone());
    }

    let chars: Vec<char> = alphabet.chars().collect();
    return sequence.into_iter().map(|i| chars[i]).collect();
}

This algorithm generates de Bruijn sequence over the provided alphabet of order n.

The function de_bruijn returns the shortest string that contains "all the possible combination of the provided alphabet of size n" as substrings. The length of the provided string is exactly k^n + (n-1) where k is the size of the provided alphabet, k^n is the size of the string cycle that contains all the substrings, and the n-1 comes from appending the first n-1 characters of the string into the end of the "broken cycle".