递归遍历具有嵌套属性的整个对象

Question

我有很多技巧(比如格斗动作(，我想从中找到所有的序列。每个对象都有一个名为"results"的属性，其中包含使用该技术后可以执行的操作。一个结果可能包含另一种技术，它本身包含多个结果，这些结果可能包含也可能不包含另一项技术，等等

我目前正在使用递归来查找这些序列，如果结果包含技术，函数会调用自己，如果结果中没有找到技术，则返回部分序列。

findSequencesRecursively(technique: Technique, partialSequence: Technique[]): Technique[] | null {
// In order to prevent a stack-overflow, sequences are capped at an arbitrary number,
// as these are likely infinite cycles as opposed to actual sequences.
if (partialSequence.length <= 25) {
for (let result of technique.results) {
if (result.technique) {
const completeSequence = this.findSequencesRecursively(
result.technique,
[...partialSequence, result.technique]
);
if (completeSequence) return completeSequence;
}
}
return partialSequence;
} else return null;
}

然而，这总是返回它找到的第一个序列，但不是所有序列。考虑以下内容：

在对象t4(肘部打击(中，有两个结果包含一种技术：

{ id: 't4r1', technique: t3, otherInfo: null };
{ id: 't4r4', technique: t2, otherInfo: 'bar' };

(技巧t3被命名为后空翻，t1被命名为膝关节动作(

算法(在其当前状态下将始终返回t4->t3并查找其结果，依此类推，但始终找不到t4->t2->t1的序列，因为始终找不到此t4-<t2序列

如何从这些对象中找到所有序列？

这里有一个StackBlitz重现了我的问题，如果你设法解决了它，你也应该看到肘部打击->蝴蝶踢->膝盖动作作为输出

Answer 1

您走的是正确的道路，只有少数细节是错误的。具体来说，你会提前返回，而不去看第二和更深的分支。

以下是一个如您所期望的那样工作的示例：

public createSequences(): void {
function findAllPaths(initialTechniques: Technique[]): SequenceData[] {
const result: SequenceData[] = [];
function walk(technique: Technique, currentPath: Technique[] = []): void {
currentPath = [ ...currentPath, technique ];
const continuations = technique.results.map(v => v.technique).filter(v => !!v);
if (continuations.length) {
continuations.forEach(t => walk(t, currentPath))
} else {
result.push({ sequentialTechniques: currentPath });
}
}
initialTechniques.forEach(t => walk(t));
return result;
}

this.sequences.push(...findAllPaths(this.data));
}

它产生的输出：

Knee-Action
Butterfly-Kick -> Knee-Action
Backflip
Elbow-Strike -> Backflip
Elbow-Strike -> Butterfly-Kick -> Knee-Action

还有StackBlitz项目，看看它在行动。

Answer 2

我将提出一些建议。我认为你应该使用构造函数来避免手工构建这么多数据-

ngOnInit() {
const t1 = new Technique('t111', 'Knee-Action', [
new Snapshot('t1r1', null, null),
new Snapshot('t1r2', null, 'foo'),
new Snapshot('t1r3', null, null),
new Snapshot('t1r4', null, 'bar'),
new Snapshot('t1r5', null, 'bas'),
])
const t2 = ...
...
}

这是一个更新你的类的问题-

class Snapshot {
id: string;
technique?: Technique;
otherInfo?: any;
constructor(id: string, technique?: Technique, otherInfo?: any) {
Object.assign(this, {id, technique, otherInfo})
}
}
class Technique {
id: string;
name: string;
results: Snapshot[];
constructor(id: string, name: string, results: Snapshot[] = []) {
Object.assign(this, {id, name, results})
}
}
class SequenceData {
sequentialTechniques: Technique[];
constructor(sequentialTechniques: Technique[]) {
Object.assign(this, {sequentialTechniques})
}
}

接下来，findSequencesRecursively和createSequences函数不需要在类上下文中纠缠在一起。您的App组件可以切中要害-

export class AppComponent implements OnInit {
public sequences: SequenceData[];
ngOnInit() {
const t1 = new Technique('t111', 'Knee-Action', [
new Snapshot('t1r1', null, null),
new Snapshot('t1r2', null, 'foo'),
new Snapshot('t1r3', null, null),
new Snapshot('t1r4', null, 'bar'),
new Snapshot('t1r5', null, 'bas'),
])
const t2 = new Technique('t211', 'Butterfly-Kick', [
new Snapshot('t2r1', null, null),
new Snapshot('t2r2', null, 'foo'),
new Snapshot('t2r3', null, null),
new Snapshot('t2r4', t1, 'bar'),
new Snapshot('t2r5', null, 'bas'),
])
const t3 = new Technique('t311', 'Backflip', [
new Snapshot('t3r1', null, null),
new Snapshot('t3r2', null, 'foo'),
new Snapshot('t3r3', null, null),
new Snapshot('t3r4', null, 'bar'),
new Snapshot('t3r5', null, 'bas'),
])
const t4 = new Technique('t411', 'Elbow-Strike', [
new Snapshot('t4r1', t3, null),
new Snapshot('t4r2', null, 'foo'),
new Snapshot('t4r3', null, null),
new Snapshot('t4r4', t2, 'bar'),
new Snapshot('t4r5', null, 'bas'),
])
const data = [t1, t2, t3, t4]
this.sequences = Array.from(graph(data), path => new SequenceData(path))
}
}

graph是一个普通的生成器函数，可以在组件类之外实现

function *graph(t): Generator<Technique[]> {
switch (t?.constructor) {
case Array:
for (const x of t)
yield *graph(x)
break
case Snapshot:
if (t.technique)
yield *graph(t.technique)
break
case Technique:
for (const snapshot of t.results)
for (const path of graph(snapshot))
yield [ t, ...path ]
yield [t]
break
default:
throw Error(`unsupported type: ${t?.constructor}`)
}
}

最终输出为

Hello!
Knee-Action
Butterfly-Kick -> Knee-Action
Butterfly-Kick
Backflip
Elbow-Strike -> Backflip
Elbow-Strike -> Butterfly-Kick -> Knee-Action
Elbow-Strike -> Butterfly-Kick
Elbow-Strike

验证堆叠式上的结果