string - 给定任意数量的不同字母，我如何找到包含所有可能的双字母序列的最短字符串？

Question

我无法解释，因为英语是我的第二语言，而且我的逻辑很糟糕。我将举例说明。

如果字母是 ABC，我要查找的有效组合是 AB、AC、BA、BC、CA、CB。简单组合成一个字符串:ABACBABCCACB但是该字符串中仍然存在重复项。如果我“压缩”它，我会得到:ABACBCA

我不确定如何更好地解释，但我正在寻找一种可以产生“压缩”版本的算法。

Answer 1

接听 jenesaisquoi 的 comment ，如果我们删除连续的重复项，则可以使用 de Brujin 序列。

JavaScript 示例(改编自 Wikipedia 上的 Python 代码)。请记住，de Brujin 序列环绕，因此我们需要包括适当的重叠以获得所有组合。

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))