# Generating combinations without getting stuck in recursive calls

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

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.
However, you can save a step by only adding the node `e` to `visited_elements` if `e.process()` is successful.
• The `visited_elements` set is the marking; the marker is visible to the algorithm and nowhere else. May 17, 2018 at 15:18
• So essentially stick with what I was doing and not removing the element from `visited_elements` if unsuccessful? May 18, 2018 at 9:08
• My mistake -- remove `e` if unsuccessful. May 18, 2018 at 14:27
• @BobDalgleish I did try that. That is essentially the last line before `return False` but, as I said, it takes forever to finish. May 21, 2018 at 14:36