一个通过调用自身解决问题的求解器
递归和生成器是解决这个问题的自然方法。我们可以使用归纳推理来为任何数字t编写segment(t) -
- 如果输入的
t小于零，则没有有效的段。停止迭代。
- (归纳)
t为非负数。如果t为零，则产生空段，[]。
- (归纳)
t为正数。产生单例段[t]，对于范围1..t中的每个 i ，对于子问题t-i*2的每个段s，对称地在段前面和后面添加 i 并产生。
function* segment(t) {
if (t < 0) return
if (t == 0) return yield []
yield [t]
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。后续的yield表达式会将两个i加到结果中，因此它们必须从子问题中减去以平衡方程。
for (const s of segment(t - i * 2))
yield [i, ...s, i]
为什么要使用递归技术？
这种方法的优点很多 -
|
|
| 静态，任意分割大小 |
❌ |
| 仅限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]
}
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) {
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))
yield [i, ...s, i]
yield [t]
}
console.log("== 18 ==")
for (const s of segment(18, 3))
console.log(s.join(" · "))
.as-console-wrapper { min-height: 100%; top: 0; }
最大段长度
类似地，可以添加max参数来控制最大段长度。避免在函数中硬编码此值，以保留对调用者的更高灵活性 -
function* segment(t, min = 0, max = t) {
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))
yield [i, ...s, i]
if (t <= max) yield [t]
}
console.log("== 18 ==")
for (const s of segment(18, 3, 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) {
if (t < min || t < init) return
if (t == 0) return yield []
for (let i = Math.max(init, min); i < t; i++)
for (const s of segment(t - i * 2, min, max, 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))
console.log(split(word, s).join(" · "))
.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 [[]]
return [
[t],
...range(1, t).flatMap(i =>
segment(t - i * 2).map(s =>
[[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
