Generating combinations without getting stuck in recursive calls

Question

This question is about figuring the design of a recursive function that changes the state of a group of elements by processing one of them at a time, with the goal of reaching a desired state.

The initial state of the elements is one that does not satisfy the requirements. We try to correct that by processing certain elements that we can target, but once an element in processed successfully, the ones related to it must be processed as well to balance out the previous action. Then, the ones related to these must be processed in turn as well, and so on, cue the recursive function.

def satisfy(e, visited_elements=set()):
 # e is an element that is in such state that is preventing the whole from being satisfied
 visited_elements.add(e)
 # the element is processed in a way that aims to satisfy the state
 if e.process():
 # if e is processed, other specific elements need to be processed too
 # these are not directly related to e, but to a group g related to e
 # processing successfully all elements in any of these groups will do
 for g in e.related_groups:
 if all([satisfy(r, visited_elements) for r in g.related_elements(exclude=visited_elements)]):
 return True
 # if processing e fails, or the related elements could not be processed, the action needs to be undone
 e.undo_process()
 # so that it can be used again in a different combination
 visited_elements.remove(e)
 return False

The solution is reached if a particular combination of elements are processed. A particular combination of elements is what we are calling a state (of the whole).

The problem with this is that the total number of combinations is so big, we get stuck in a very long chain. The only way to guarantee it is stopped at a reasonable time is removing visited_elements.remove(e), but then we would be greatly reducing the space of states to visit, and we would be disregarding possible solutions.

So when we have a recursive function that generates combinations or states which could potentially take very long, what can we do to limit it?

If the answer is coming up with a stopping conditions, what can I do to help me identify what is a good stopping condition for my problem when there is no easy way to help the algorithm make a better decision? (the decision here would be what elements to process first, and what related group or groups look more promising than the rest)

Answer 1

You are performing a traversal of a directed graph using a Depth First Search. You need to mark each node you visit so you don't visit it again. In your case, you mark nodes by adding them to visited_elements. Your algorithm will succeed when all nodes reachable from your starting node have been processed.

Your algorithm must visit all nodes once, and, with marking, only once. So, there is no way to particularly speed it up.

However, you can save a step by only adding the node e to visited_elements if e.process() is successful.

• Robert Harvey: You have to remember the nodes you visited, not necessarily mark them. Marking implies modifying the node; you should be able to perform your search without doing that.
• BobDalgleish: The visited_elements set is the marking; the marker is visible to the algorithm and nowhere else.
• dabadaba: So essentially stick with what I was doing and not removing the element from visited_elements if unsuccessful?
• BobDalgleish: My mistake -- remove e if unsuccessful.
• dabadaba: @BobDalgleish I did try that. That is essentially the last line before return False but, as I said, it takes forever to finish.