以递归的方式找到所有可能的路径

Question

抱歉，因为这个问题对很多人来说可能听起来很菜鸟，但我绝对不擅长递归，需要一些帮助。

这是模型：

struct Chain {
    let initialId: Int
    let chains: [SubChain]
}

struct SubChain {
    let id: Int
    let subChains: [SubChain]
    
    init(_ id: Int, subChains: [SubChain] = []) {
        self.id = id
        self.subChains = subChains
    }
}

一个例子：

let chain = Chain(
    initialId: 1,
    chain: [
        SubChain(
            2,
            subChains: [
                SubChain(3),
                SubChain(4)
            ]
        ),
        SubChain(
            5,
            subChains: [
                SubChain(6),
                SubChain(
                    7,
                    subChains: [
                        SubChain(8)
                    ]
                )
            ]
        ),
        
    ]
)

现在我想找到所有可能的路径，即：

1 -> 2 -> 3

1 -> 2 -> 4

1 -> 5 -> 6

1 -> 5 -> 7 -> 8

我在 Chain 开始写这个，但我不知道如何递归地写这个。

var straightChain: [[Int]] {
    var result: [[Int]] = []
    for subChain in chain {
        for c in subChain.subChains {
            var subResult: [Int] = [initialId, subChain.id]



            result.append(subResult)
        }
    }
    return result
}

你能帮帮我吗？感谢您的帮助

Answer 1

链和子链不需要两种不同的结构类型。

对于递归，你需要做一个函数，它必须总是有一个基本情况，以及一个减少的情况问题每次都下降一点，调用自己

struct Node {
    let id: Int
    let children: [Node]
}


let n = Node(
    id: 1,
    children: [
        .init(id: 2, children: [
            .init(id: 3, children: []),
            .init(id: 4, children: [])
        ]),
        .init(id: 5, children: [
            .init(id: 6, children: []),
            .init(id: 7, children: [
                .init(id: 8, children: [])
            ])
        ])
    ])

func paths(from n: Node) -> [[Int]] {
    if n.children.isEmpty {
        return [[n.id]]
    }
    else {
        var result: [[Int]] = []
        for childPath in n.children.flatMap(paths(from:)) {
            result.append([n.id] + childPath)
        }
        return result
    }
}

paths(from: n)

您可能想让您的结构通用化：

struct Node<T> {
    let id: T
    let children: [Node<T>]    
}


let example = Node<Int>(....etc)

func paths<T>(from n: Node<T>) -> [[T]] {
    // Base case, this stops the recursion so it doesn't go on forever
    if n.children.isEmpty {
        return [[n.id]]
    }
    else {
        // reduce the problem a bit by working on just the children of this node, adding in our value later on
        var result: [[T]] = []
        // recursive call to our own function, which now has a smaller problem to work on and will always be closer to the base case
        for childPath in n.children.flatMap(paths(from:)) {
            result.append([n.id] + childPath)
        }
        return result
    }
}

如果您愿意，您可以将子路径表达为结构的扩展，例如：

extension Node {
    func subPaths() -> [[T]] {
        if children.isEmpty {
            return [[id]]
        }
        else {
            var result: [[T]] = []
            for childPath in children.flatMap({ [=12=].subPaths() }) {
                result.append([id] + childPath)
            }
            return result
        }
    }
}

n.subPaths()

或者也许：

extension Node {
    func subPaths() -> [[T]] {
        if children.isEmpty {
            return [[id]]
        }
        else {
            return children.flatMap({ [=13=].subPaths() })
                .map { [id] + [=13=] }
        }
    }
}

Answer 2

这是您问题的答案

下面是子链的递归

func findAllPossibleSubChain(_ chain: SubChain) -> [[Int]] {
    if chain.subChains.count == 0 {
        return [[chain.id]]
    }

    var result : [[Int]] = []

    for sub in chain.subChains {
        let temp = findAllPossibleSubChain(sub)
        for val in temp {
            // Recursion for the subChain if have array
            result.append([chain.id] + val)
        }
    }

    return result
}

主要

var result : [[Int]] = []
// Because of chain only have 1
if chain.chains.count == 0 {
        result = [[chain.initialId]]
} else {
        for sub in chain.chains {
             let temp = findAllPossibleSubChain(sub)
             for val in temp {
                result.append([chain.initialId] + val)
             }
        }
}

print("result: ", result) // result:  [[1, 2, 3], [1, 2, 4], [1, 5, 6], [1, 5, 7, 8]]

以递归的方式找到所有可能的路径

Find all possible paths in a recursive way

recursion

swift