javascript - 如何在 JavaScript 中对称拆分字符串？

Question

我正在尝试在 JavaScript 中对称拆分字符串。我的意思是，如果是 8 个字符，则将其分成 2 个 block 。如果是 9 个字符，则将其分成 3 个 block 。如果是 n 个字符，则将其分成 2 block 和 3 block ，使其形成镜像图像在中心。

const segmentNumber = (value) => {
  let array = value.split('')
  if (array.length % 3 === 0) {
    return chunkArray(array, 3).join('·')
  } else if (array.length % 2 === 0) {
    return chunkArray(array, 2).join('·')
  } else {
    let reversed = array.slice().reverse()
    let a = 0
    let ar = []
    let zr = []
    while (true) {
      ar.push(array.slice(a, a + 2).join(''))
      zr.push(reversed.slice(a, a + 2).join(''))
      array = array.slice(a + 2)
      reversed = reversed.slice(a + 2)
      a += 2
      let modulus
      if (array.length % 3 === 0) {
        modulus = 3
      } else if (array.length % 2 === 0) {
        modulus = 2
      }
      if (modulus) {
        return ar.concat(chunkArray(array, modulus)).concat(zr.reverse())
      }
    }
  }

  return
}

function chunkArray(arr, len) {

  var chunks = [],
      i = 0,
      n = arr.length;

  while (i < n) {
    chunks.push(arr.slice(i, i += len));
  }

  return chunks;
}

我可以将字符串分 block ，但不确定如何使其对称分 block 。例如:

10: 2-3-3-2

11: 2-2-3-2-2

12: 3-3-3-3

13: 2-3-3-3-2

你是如何产生这种图案的，小的数字在外面，大的数字 3 朝中心，所以它形成了一个镜像？
我如何改进我正在实现的内容？

Answer 1

通过调用自身 来求解的求解器
递归和生成器是这个问题的自然解决方案。我们可以使用inductive reasoning为任何数字写段(t)，t -

如果输入 t小于零，则没有有效段。停止迭代

(感应)t是非负的。如果 t为零，产生空段，[]

(感应)t是积极的。产生单例段，[t] , 对于每个 i范围 1.. t , 对于每个段 s子问题的t - i * 2 , 对称地前置和附加 i到段和产量

function* segment(t) {
  if (t < 0) return               // 1
  if (t == 0) return yield []     // 2
  yield [t]                       // 3
  for (let i = 1; i < t; i++)
    for (const s of segment(t - i * 2))
      yield [i, ...s, i]
}

console.log("== 7 ==")
for (const s of segment(7))
  console.log(s.join(" · "))
  
console.log("== 8 ==")
for (const s of segment(8))
  console.log(s.join(" · "))

.as-console-wrapper { min-height: 100%; top: 0; }

== 7 ==
7
1 · 5 · 1
1 · 1 · 3 · 1 · 1
1 · 1 · 1 · 1 · 1 · 1 · 1
1 · 2 · 1 · 2 · 1
2 · 3 · 2
2 · 1 · 1 · 1 · 2
3 · 1 · 3

== 8 ==
8
1 · 6 · 1
1 · 1 · 4 · 1 · 1
1 · 1 · 1 · 2 · 1 · 1 · 1
1 · 1 · 1 · 1 · 1 · 1 · 1 · 1
1 · 1 · 2 · 2 · 1 · 1
1 · 2 · 2 · 2 · 1
1 · 2 · 1 · 1 · 2 · 1
1 · 3 · 3 · 1
2 · 4 · 2
2 · 1 · 2 · 1 · 2
2 · 1 · 1 · 1 · 1 · 2
2 · 2 · 2 · 2
3 · 2 · 3
3 · 1 · 1 · 3
4 · 4

为什么t - i * 2 ?
子问题是 t - i * 2 , 或 t减二 i s。随后的产量表达式是添加两个 i结果，因此必须从子问题中减去它们以平衡方程 -

for (const s of segment(t - i * 2)) // subtract two i from t
  yield [i, ...s, i]                // add two i to the segment

为什么是递归技术？
这种方法的优点很多 -





静态的，任意分割大小
❌

只有 2 和 3
❌

模数运算
❌

条件变量赋值
❌

数组 .slice或 .reverse❌

硬编码 .join❌

字符串到数字的转换
❌
parseInt❌

除法和四舍五入
❌

找到的每个组合
✅

两个局部变量
✅

两个简单的 if条件
✅

暂停、恢复或取消
✅


可视化
给定 segment(4) -

[4]                                  // t = 4

[1,            , 1]
    \        /
      ...[2]                         // t = 2

[1,                           , 1]
    \                       /
      ...[1,           , 1]
             \       /
               ...[]                 // t = 0

[2,           , 2]
    \       /
      ...[]                          // t = 0

[3,           , 3]
    \       /
      ...❌                         // t = -2

[4]
[1,2,1]
[1,1,1,1]
[2,2]

更改输出排序
这不需要对算法进行外科手术重新布线或调整您对问题的思考方式。通过更改 yield 的顺序表达式，你改变输出的顺序 -

function* segment(t) {
  if (t < 0) return
  if (t == 0) return yield []
  for (let i = 1; i < t; i++)
    for (const s of segment(t - i * 2))
      yield [i, ...s, i]
  yield [t]   // ✅ yield singleton segment last
}

console.log("== 7 ==")
for (const s of segment(7))
  console.log(s.join(" · "))

.as-console-wrapper { min-height: 100%; top: 0; }

== 7 ==
1 · 1 · 1 · 1 · 1 · 1 · 1
1 · 1 · 3 · 1 · 1
1 · 2 · 1 · 2 · 1
1 · 5 · 1
2 · 1 · 1 · 1 · 2
2 · 3 · 2
3 · 1 · 3
7

最小段长度
也许您希望最小的段是 2或 3 .通过添加 min参数，这可以由调用者决定，而不是硬编码到 segment功能 -

function* segment(t, min = 0) { // ✅ add min parameter
  if (t < min) return              // ✅ t < min
  if (t == 0) return yield []
  for (let i = Math.max(1, min); i < t; i++) // ✅ max(1, min)
    for (const s of segment(t - i * 2, min)) // ✅ pass min
      yield [i, ...s, i]
  yield [t]
}

console.log("== 18 ==")
for (const s of segment(18, 3)) // ✅ segments of 3 or greater
  console.log(s.join(" · "))

.as-console-wrapper { min-height: 100%; top: 0; }

最大段长度
以类似的方式， max可以添加参数来控制最大段长度。避免在函数中对它进行硬编码，以便为调用者保留更高的灵 active -

function* segment(t, min = 0, max = t) { // ✅ add max parameter
  if (t < min) return
  if (t == 0) return yield []
  for (let i = Math.max(1, min); i < t; i++)
    for (const s of segment(t - i * 2, min, max)) // ✅ pass max
      yield [i, ...s, i]
  if (t <= max) yield [t] // ✅ if (t <= max)
}

console.log("== 18 ==")
for (const s of segment(18, 3, 8)) // ✅ segments between 3 and 8
  console.log(s.join(" · "))

.as-console-wrapper { min-height: 100%; top: 0; }

== 18 ==
3 · 3 · 6 · 3 · 3
3 · 4 · 4 · 4 · 3
4 · 3 · 4 · 3 · 4
5 · 8 · 5
6 · 6 · 6
7 · 4 · 7

向中心增加
如果您希望数字向中心增加，则需要添加另一个可配置参数 init。 .如您所见，只需对原始算法进行细微调整即可仔细添加每个细微差别的标准 -

function* segment(t, min = 0, max = t, init = 1) { // ✅ init = 1
  if (t < min || t < init) return // ✅ || t < init
  if (t == 0) return yield []
  for (let i = Math.max(init, min); i < t; i++) // ✅ init
    for (const s of segment(t - i * 2, min, max, i + 1)) // ✅ i + 1
      yield [i, ...s, i]
  if (t <= max) yield [t]
}

console.log("== 36 ==")
for (const s of segment(36, 2, 9))
  console.log(s.join(" · "))

.as-console-wrapper { min-height: 100%; top: 0; }

== 36 ==
2 · 3 · 4 · 5 · 8 · 5 · 4 · 3 · 2
2 · 5 · 7 · 8 · 7 · 5 · 2
3 · 4 · 7 · 8 · 7 · 4 · 3
3 · 5 · 6 · 8 · 6 · 5 · 3

拆分字符串
要拆分字符串，我们可以写 split它接受一个字符串和一个由 segment 返回的值-

const split = (t, [s, ...segments]) =>
  s == null
    ? []
    : [t.substring(0, s), ...split(t.substring(s), segments)]

function* segment(t) {
  if (t < 0) return
  if (t == 0) return yield []
  for (let i = 1; i < t; i++)
    for (const s of segment(t - i * 2))
      yield [i, ...s, i]
  yield [t]
}
    
const word = "function"
for (const s of segment(word.length)) // ✅ segment word.length
  console.log(split(word, s).join(" · ")) // ✅ split word using s

.as-console-wrapper { min-height: 100%; top: 0; }

f · u · n · c · t · i · o · n
f · u · n · ct · i · o · n
f · u · nc · ti · o · n
f · u · ncti · o · n
f · un · c · t · io · n
f · un · ct · io · n
f · unc · tio · n
f · unctio · n
fu · n · c · t · i · on
fu · n · ct · i · on
fu · nc · ti · on
fu · ncti · on
fun · c · t · ion
fun · ct · ion
func · tion
function

优化
您可以通过消除对某些组合的检查来加速算法。外 for循环从 1.. t但可以缩短为 1.. Math.floor(t/2) .这提高了 segment 的性能但增加了一些复杂性。为了清楚起见，这被遗漏了，仍然是读者的更新。
不带发电机
尽管生成器非常适合组合数学问题，但它们不是必需的。我们可以将整个程序提升到一个数组上下文中，并拥有 segment返回结果数组而不是迭代器。请注意，人机工程学不太好，数据嵌套级别已强制增加一。然而，它确实遵循与原始算法相同的归纳推理 -

function segment(t) {
  if (t < 0) return []            // if (t < 0) return 
  if (t == 0) return [[]]         // if (t == 0) return yield []
  return [                        //   
    [t],                          // yield [t]
    ...range(1, t).flatMap(i =>   // for (let i = 0; i<t; i++)
      segment(t - i * 2).map(s => //   for (const s of segment(t - i * 2))
        [[i, ...s, i]]            //     yield [i, ...s, i]
      )
    )
  ]
}

function range(a, b) {
  return Array.from(Array(b - a), (_, n) => n + a)
}

console.log("== 7 ==")
for (const s of segment(7))
  console.log(s.join(" · "))

== 7 ==
7
1,5,1
1,1,3,1,1
1,1,1,1,1,1,1
1,2,1,2,1
2,3,2