Given an arbitrary number of different letters, how can i find the shortest string that will contain all possible two-letter sequences?

Question

I'm having trouble explaining because English is my second language and I'm bad at logic. I'll give examples to help.

If letters are ABC, the valid combinations I'm looking for are AB,AC,BA,BC,CA,CB. Simply combined into a string: ABACBABCCACB But there are still duplicates in that string. If I "compress" it, I get: ABACBCA

I'm not sure how to explain better, but I'm looking for an algorithm that would produce the "compressed" version.

I believe what you are looking for is a *de Bruijn* sequence — Rorschach, Sep 15 '19 at 20:26
@jenesaisquoi nvm, it does when we consider that it wraps around. — גלעד ברקן, Sep 15 '19 at 21:05
right, to get the exact result here, using the algorithm on the wiki page w/o modification, you'd append the first char to the end and remove subsequent duplicates (or `n-1` in the general case) — Rorschach, Sep 15 '19 at 21:07

score 2 · Accepted Answer · answered Sep 15 '19 at 21:17

To pick up on jenesaisquoi's comment, the de Brujin sequence can be used if we remove the consecutive duplicates.

Example in JavaScript (adapted from the Python code on Wikipedia). Remember that the de Brujin sequence wraps around so we would need to include the appropriate overlap to get all the combinations.

function de_bruijn(k, n){
  /***
  de Bruijn sequence for alphabet k
  and subsequences of length n.
  ***/
  var alphabet
  
  if (typeof k == 'number'){
    alphabet = new Array(k).fill(null)
      .map((_, i) => String(i))
    
  } else if (typeof k == 'string'){
    alphabet = k
    k = k.length
  }

  var a = new Array(k * n).fill(0)
  var sequence = []

  function db(t, p){
    if (t > n){
      if (n % p == 0)
        sequence = sequence.concat(
          a.slice(1, p + 1))
        
    } else{
      a[t] = a[t - p]
      db(t + 1, p)
      for (let j=a[t-p]+1; j<k; j++){
        a[t] = j
        db(t + 1, t)
      }
    }
  }
 db(1, 1)

  return sequence.map(i => alphabet[i])
    .join("")
}

// https://stackoverflow.com/questions/30716829/how-to-remove-repeated-entries-from-an-array-while-preserving-non-consecutive-du
function removeDuplicates(str){
  return str.split("").filter(function(item, pos, arr){
    return pos === 0 || item !== arr[pos-1]; }
  ).join("")
}

var result = de_bruijn(3, 2)
console.log(result)
console.log(removeDuplicates(result))

result = de_bruijn("abc", 2)
console.log(result)
console.log(removeDuplicates(result))

This is fantastic! Thanks you so much :) Just FYI: This will be used to optimize my guitar practice, chord changes specifically. Thanks a bunch! — Kerans, Sep 16 '19 at 03:16

Given an arbitrary number of different letters, how can i find the shortest string that will contain all possible two-letter sequences?

1 Answers1