Performance Problems
Your current solution works decent for small cases, but there are a few problems when the problem starts to scale up, which causes the performance to drop. I will mention the two biggest I have found.
- You construct all paths toward the goal, even the unviable ones, in full until you remove them. This causes an exponential amount of extra paths to tried (though you might also have exponential amount of results).
- The
+ on lists causes full rebuilding of the lists, which causes a single path to cost O(n^2) to construct. Note that this cost is shared with some of the other paths investigated, which may cause the amortized cost to still be O(n) when you share it with exponential amount of paths.
Note that the first problem may overshadow the second, and that if the smallest move is a common divisor of all the other moves and the result, then early prunning of paths is impossible (because they may only make a mistake on the last step).
Solution
We seperate the solution into the subsections that resolve each of the problems mentioned in the problem section, and a subsection for the combined result. The way presented here is just one way to solve the above mentioned problem in a way that remains close to the OP.
Early Prunning
To solve the problem of exponentially many paths that lead to no result, we can try to find a way to early stop a path early on if we know that it cannot possible lead to a result. If we have a function that tells us whether we can walk a certain distance we can implement valid_moves in this simple form (note I changed the names valid_moves->valid_paths, legal->moves, and permutations->results and I will be using these names going forward):
def valid_paths(position, target, moves, path, results, is_legal=lambda x: x >= 0):
for move in moves:
new_position = position + move
if is_legal(target - new_position):
new_path = path + [move]
if new_position == target:
results.append(new_path)
else:
valid_moves(new_position, target, moves, new_path, results)
return results
So how do we construct a usefull is_legal function? One way to do this is to construct all the reachable path lengths and check if the remaining distance is such a reachable path. The way I will show here to construct all the reachable paths lengths is through dynamic programming:
def construct_is_legal(moves, distance):
if not moves:
return lambda length: length==0
lengths_to_check = [move for move in moves]
lengths_reachable = {move for move in moves}
min_length = min(lengths_to_check) # used by shortcut
if distance % min_length and all(move % min_length == 0 for move in moves):
return lambda length: length >= 0 and length % min_length
while lengths_to_check:
move = lengths_to_check.pop()
lengths_to_add = []
for length in lengths_reachable:
new_length = length+move
if new_length not in lengths_reachable and new_length <= distance:
lengths_to_add.append(new_length)
for new_length in lengths_to_add:
lengths_to_check.append(new_length)
lengths_reachable.add(new_length)
lengths_reachable.add(0) # we can always reach the same place
return lambda length: length in lengths_reachable
Note that we use sets to have fast checks for inclusion (they are implemented kind of like hash-tables under the hood according to this answer), so we can expect the assymtotic cost to be below of the brute force test of each possible path, as we only check once for each reached position and not for every way to reach said position.
Also note that I added some special cases (no results and every number divisiable by the lowest move), so we do not do all the extra work when there is a simple solution to the problem.
Delayed Concatenation
To solve the problem of O(n^2) cost for building a result (now more relevant since we have cut out the extra false paths it might have been sharing the cost with), we need to ensure we do not have to build the full list when we branch out several versions of it. We can do this by reversed directed linked tree, where each node is a move and point toward the move it took previously. Here is a simple implementation of it:
class Path:
def __init__(self,value, prev=None):
self.value = value
self.prev = prev
def to_list(self):
result = [self.value]
prev = self.prev
while previs not None:
result.append(prev.value)
prev = parent.prev
result.reverse()
return result
We can then replace the new_path = path + [move] with new_path = Path(move, prev=path), and when we add a result we also need to replace results.append(new_path) with results.append(new_path.to_list()). We could also just add the Path objects and let the user convert them to lists of moves when they need to, since the space complexity of storing many similar paths is much lower due to reuse of space for shared parts of the paths.
Combined
We now need to combine the parts into a whole solution. For convinience I have combined many of the tedious parts of the original into a function, which handle the combined solution:
class Path:
def __init__(self,value, prev=None):
self.value = value
self.prev = prev
def to_list(self):
result = [self.value]
prev = self.prev
while previs not None:
result.append(prev.value)
prev = parent.prev
result.reverse()
return result
def construct_is_legal(moves, distance):
if not moves:
return lambda length: length==0
lengths_to_check = [move for move in moves]
lengths_reachable = {move for move in moves}
min_length = min(lengths_to_check) # used by shortcut
if distance % min_length and all(move % min_length == 0 for move in moves):
return lambda length: length >= 0 and length % min_length
while lengths_to_check:
move = lengths_to_check.pop()
lengths_to_add = []
for length in lengths_reachable:
new_length = length+move
if new_length not in lengths_reachable and new_length <= distance:
lengths_to_add.append(new_length)
for new_length in lengths_to_add:
lengths_to_check.append(new_length)
lengths_reachable.add(new_length)
lengths_reachable.add(0) # we can always reach the same place
return lambda length: length in lengths_reachable
def list_paths(position, target, moves, path, results, is_legal=lambda x: x >= 0):
for move in moves:
new_position = position + move
if is_legal(target - new_position):
new_path = Path(move, prev=path)
if new_position == target:
results.append(new_path.to_list())
else:
valid_moves(new_position, target, moves, new_path, results)
return results
def valid_paths(target, moves, start=0):
is_legal = construct_is_legal(moves, target-start)
if is_legal(target-start):
return list_paths(start, target, moves, path=None, result=[], is_legal=is_legal)
else:
return [] # no paths exist
if __name__ == '__main__':
print(*valid_paths(3, [1, 2]), sep='\n')
Note that we have wrapped many of the annoying parts of the interface into the new valid_paths, and had it also handle the special case of no possible results early on.
Alternative
You may have noticed that the construction in is_legal is fairly close to actually solving the full problem, and we can indeed solve the entire problem with this dynamic programming approach
by changing the set lengths_reachable from a set to a dictionary of combinations we can reach a given length with. Once we have such a dictionary we can easily list the paths by going from the full distance and recursively divide up the problem into the possible subpaths and then combine all the results. Here is an implementation:
def chain(*generators):
for generator in generators:
yield from generator
def dynamic_build(moves, distance):
""" Build a dictionary of possible subpath decomposition up to distance"""
lengths_to_check = [move for move in moves]
lengths_reachable = {move:{move} for move in moves}
while lengths_to_check:
move = lengths_to_check.pop()
lengths_to_add = {}
for length in lengths_reachable:
new_length = length+move
lower, upper = (move, length) if move <= length else (length, move)
if new_length <= distance:
if new_length in lengths_reachable:
lengths_reachable[new_length].add((lower,upper))
else:
if new_length in lengths_to_add:
lengths_to_add[new_length] = {(lower, upper)}
else:
lengths_to_add[new_length].add((lower, upper))
for new_length in lengths_to_add:
lengths_to_check.append(new_length)
lengths_reachable[new_length]= lengths_to_add[new_length]
return lengths_reachable
def list_paths(lengths_reachable, target):
main_node = lengths_reachable[target]
results = []
for way in main_node:
if len(way) == 1:
results.append([way])
else:
lower, upper = way
lower_results = list_paths(lengths_reachable, lower)
upper_results = list_paths(lengths_reachable, upper)
for low_path in lower_results:
for high_path in upper_results:
results.append(chain(low_path, high_path))
results.append(chain(high_path, low_path))
return results
def valid_paths(target, moves, start=0):
distance = target - start
lengths_reachable = dynamic_build(moves, distance)
if distance not in lengths_reachable:
return []
return list(map(list, list_paths(lengths_reachable, distance)))
if __name__ == '__main__':
print(*valid_paths(3, [1, 2]), sep='\n')
While the work of the alternative is about as much as the other solution, it does provide some more information about the solution, which may be usefull in related problems.
Notes
It should be noted that both the original and the solutions provided here all make use of recoursion. The problem is that python does not really like deep recursion (it has poor performance, to the point where the recursion stack is limited to about 1000). This problem is close to exponential in this depth though, so we need some fairly special cases for us to not run into other problems first. If we are indeed in such special cases, then we would need to change the above algorithms from recursive formulation to loop based versions or find a new alternative of this form.
