a solver that solves by calling itself
递归和生成器是这个问题的自然解决方案.我们可以用inductive reasoning-
- 如果输入
t
小于零,则不存在有效段.停止迭代
- (感应)
t
是非负的.如果t
为零,则产生空段[]
- (感应)
t
为正.产生单子段[t]
,对于范围1.中的每一个i
..t
,对于子问题t - i * 2
的每个段s
,对称地预先加上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
why 100?
子问题是t - i * 2
,或者t
减go 两个i
.接下来的屈服表达式是将两个i
加到结果中,因此必须从子问题中减go 它们,以平衡方程-
for (const s of segment(t - i * 2)) // subtract two i from t
yield [i, ...s, i] // add two i to the segment
why recursive technique?
这种方法的优点很多-
|
|
static, arbitrary split sizes |
❌ |
only 2's and 3's |
❌ |
modulus arithmetic |
❌ |
conditional variable assignments |
❌ |
array .slice or .reverse |
❌ |
hard-coded .join |
❌ |
string-to-number conversion |
❌ |
parseInt |
❌ |
division and rounding |
❌ |
every combination found |
✅ |
two local variables |
✅ |
two simple if conditions |
✅ |
pause, resume, or cancel |
✅ |
visualization
给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]
change output ordering
这不需要对算法进行外科手术重新布线,也不需要按照您思考问题的方式进行调整.通过更改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
minimum segment length
也许你希望最小的部分是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; }
maximum segment length
以类似的方式,可以添加一个max
参数来控制最大分段长度.避免在函数中对此进行硬编码,以提高调用者的灵活性-
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
increasing toward the center
如果你想让数字向中间增加,那就需要添加另一个可配置参数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 the string
要拆分一个字符串,我们可以写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
optimization
通过取消对某些组合的判断,可以加快算法的速度.外部for
循环从1开始..t
但可以缩短为1..Math.floor(t/2)
.这提高了segment
的性能,但增加了一些复杂性.为了清楚起见,这篇文章被省略了,读者可以继续阅读.
without generators
虽然生成器非常适合组合数学问题,但它们不是必需的.我们可以将整个程序提升到一个数组上下文中,让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