Recursion - how do you extract from specific traversals

Lets say you have a string: abcde

And a set of strings: ab, cde, abcd, a, bcd, cd

You want to find all possible concatenations from the set that form the string.

You can use recursion to traverse through all possible concatenations from the set, but how would you return only those that satisfy the solution?

The possible combinations:

ab - cde - yes
ab - cd - no
abcd - no
a - bcd - no
ab - cd - no

You can build a tree from the traverse and then extract the paths that complete. Is there a way without using a tree?

I am implementing this in Python but feel free to answer in any language.


Asked by: Julian639 | Posted: 06-12-2021






Answer 1

One possibility is to structure the search as a generator. In python, it might look like this:

def concatenations(target_string, fragments, concat_path=()):
    if not target_string:
        yield concat_path
    else:
        for frag in fragments:
            if target_string.startswith(frag):
                new_target = target_string[len(frag):]
                new_path = concat_path + (frag,)
                for c in concatenations(new_target, fragments, new_path):
                    yield c

Note that I have assumed that the elements from the set can occur more than once in the string. If that is inappropriate, replace fragments by fragments - {frag} in the recursive call.

You can get all elements by just gathering all the results from the generator into a list:

fragments = {"ab", "cde", "abcd", "a", "bcd", "cd", "e"}
list(concatenations("abcde", fragments))

This produces:

[('a', 'bcd', 'e'), ('abcd', 'e'), ('ab', 'cde'), ('ab', 'cd', 'e')]

You could also accumulate all the results into a list as the search proceeds.

Answered by: Anna103 | Posted: 07-01-2022



Answer 2

Make the recursive function return a list of all concatenations.

I.e., you make a function concatenations, with a string and a set as input. This function returns a list of all concatenations of items from the set that fit the string.

Then you can define concatenations recursively in terms of itself:

  • (end condition) if the string is empty, then any set satisfies the condition, so return a list with a single, empty, concatenation.

    concatenations("", any set) = [[]]   # single empty concatenation
    
  • (recursive call) otherwise, the set of concatenations of the elements of the set that make up the string can be defined as the concatenation of an element X of the set with all concatenations of the string with X removed (from the start) and the set with X removed, for all X with which the string starts.

    concatenations(s, set) =
      sum([[[x] + y for y in concatenations(s[len(x):], set - x))]
           for x in set if s.startswith(x)], [])
    

(code is half python, half math; I hope this gives enough hints :p)

Answered by: Melissa235 | Posted: 07-01-2022



Answer 3

The way without using a tree is to just try it by going over all possible permutations, but as soon as you add any intelligence to this randomness, I have the impression you'd go back to a tree like structure again.

That said, a trie structure sounds fit for that. Two popular Python implementations are available for implementing this, trie and PyTrie.

Answered by: Cadie445 | Posted: 07-01-2022



Similar questions

recursion - Traverse tree and return a node instance after n traversals in python

The end goal is to copy a node from one tree to another tree. I want to visit each node in a binary tree and return a node instance after a number of traverses. I cannot seem to figure out how to return a specific node. Every time the node returned matches the id of the root node since I pass the root node to the function. class node(): def __init__(self): self.parent = None self.left =...


arrays - Can parallel traversals be done in MATLAB just as in Python?

Using the zip function, Python allows for loops to traverse multiple sequences in parallel. for (x,y) in zip(List1, List2): Does MATLAB have an equivalent syntax? If not, what is the best way to iterate over two parallel arrays at the same time using MATLAB?


python - Writing traversals to a file in python3.x issue

I am trying to traverse a heap, and write the traversal to a file but I am failing miserably. I keep getting an issue with the maximum traversal depth that spams my terminal when all I want is for the node to be printed out in the file.


recursion - Traverse tree and return a node instance after n traversals in python

The end goal is to copy a node from one tree to another tree. I want to visit each node in a binary tree and return a node instance after a number of traverses. I cannot seem to figure out how to return a specific node. Every time the node returned matches the id of the root node since I pass the root node to the function. class node(): def __init__(self): self.parent = None self.left =...


algorithm - Tree Traversals, recursion is faster than iteration in python?

I have implement tree preorder traversal in python, but found that my recursive version is faster than iteration version. code is as below: from __future__ import print_function import time class Tree(): def __init__(self, value): self.value = value self.left = None self.right = None def build_tree(string): nodes = [0] + [Tree(s) for s in string] for i in range...


python - Can a directed graph have two DFS traversals?

Here is my DFS traversal algorithm (Recursive approach): def dfs(v,visited) : for i in Graph[v] : if i not in visited : visited.append(i) print(i) dfs(i,visited) n = int(input()) Graph = {} for i in range(n) : name= input(print("Enter ",i+1," vertex name")) list...


python - Traversals of Binary Trees

I am trying to implement in-order, pre-order, and post-order traversals of a binary tree. My implementation seems to work for trees with a small number of nodes (as I have checked by hand) but the online software I am using says there are cases that my implementation fails (it does not provide the input that causes my implementation to fail). I have looked through several other threads on this site but cannot seem to find ...






Still can't find your answer? Check out these communities...



PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python



top