以遞回方式查找所有可能的路徑

抱歉，因為這個問題對很多人來說可能聽起來很菜鳥，但我絕對不擅長遞回，需要一些幫助。

這是模型：

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
}

你能幫我么？感謝您的幫助

uj5u.com熱心網友回復：

Chain 和 SubChain 不需要兩種不同的結構型別。

對于遞回，您需要創建一個函式，并且它必須始終有一個基本案例，以及一個每次都將問題減少一點的案例，呼叫自己

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({ $0.subPaths() }) {
                result.append([id]   childPath)
            }
            return result
        }
    }
}

n.subPaths()

也許：

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

uj5u.com熱心網友回復：

這是您問題的答案

下面是子鏈的遞回

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]]

標籤：迅速 递归

上一篇：Julia中的遞回函式

下一篇：批處理問題：無法遍歷字串變數