Sorry because this question may sound very noob for a lot of people but I am absolutely bad at recursion and need some help.

Here is the model:

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

An example:

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

Now I would like to find all the possible paths, which would be:

1 -> 2 -> 3

1 -> 2 -> 4

1 -> 5 -> 6

1 -> 5 -> 7 -> 8

I started writing this in Chain but I have no idea how to to this recursively.

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
}

Can you please help me? Thank you for your help

CodePudding user response：

Here is the answer for your question

Below is the recursion for subchain

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
}

Main

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

CodePudding user response：

You don't need two different struct types for Chain and SubChain.

For recursion, you need to make a function, and it has to always have a base case, and a case that reduces the problem down a bit each time, calling itself

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)

You might like to make your structure generic:

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

And if you like you can express the subpaths as an extension on your struct like:

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()

or perhaps:

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