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

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.

1 answer

  • answered 2019-09-15 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))