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)