string - 使用哪种算法将字符串序列排序为 block ，避免以某个元素开头？

Question

假设有一个列表:['a', 'a', 'a', 'b', 'a', 'a', 'b', 'b', 'b'] 。

您可以使用哪种算法将其分类为具有 2-4 个元素的组？ 以'b'开头的组应该尽可能少。

在这个例子中:aa |阿坝 | abbb

这是寻找最优算法的作业。

Answer 1

如果允许我们改变元素的顺序，问题就微不足道了:只需将所有 a 分组并在每个 之后插入三个 b a 在可能的情况下，创建大小为 4 的组(如果没有足够的 b，则创建更少的组)。之后，如果还有剩余的b，将它们分组，大小为4；否则，根据需要对剩余的 a 进行分组。

如果我们必须保持元素顺序，问题会变得更有趣，我们可以在 O(n) 中解决它，其中 n 是元素的数量，使用以下循环:令 f(i, j) 表示在索引 i 的最佳集合中以 b 开头的组数，其中此元素是其组中的第 j 个元素。 (由于 j 的范围是 2 到 4，复杂度是 O(3n) = O(n)。)那么:

f(i, j) =
  if A[i - j + 1] == 'b':
    return 1 + min(f(i - j, k)), for 1 < k < 5
  else:
    return min(f(i - j, k)), for 1 < k < 5

JavaScript 中的自上而下:

function f(A, i, j){
  if (j > i + 1 || i == 0)
    return Infinity
  if (i == 1)
    return A[0] == 'b' ? 1 : 0

  let prev = Infinity
  
  for (let k=2; k<5; k++)
    prev = Math.min(f(A, i - j, k), prev)
    
  return prev + (A[i - j + 1] == 'b' ? 1 : 0)
}

var A = "aaabaabbb"
console.log(A)
for (let j=2; j<5; j++)
  console.log(`If the last char is ${j + [,,'nd','rd','th'][j]}, then optimal is ${f(A, A.length-1, j)}`)

A = "aaabaabbbb"
console.log('\n' + A)
for (let j=2; j<5; j++)
  console.log(`If the last char is ${j + [,,'nd','rd','th'][j]}, then optimal is ${f(A, A.length-1, j)}`)