I’m creating “Boggle” in python, and I have a list of tuples that represent coordinates on a game board:
all_coordinates = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (2, 3)]
I’m trying to create a new list of lists of tuples that will represent all possible paths on the board.
It’d look something like this:
[[(0,0),(1,0)], ... , [(0,0),(1,0),(2,0),(2,1)] , ... , [(2, 1), (2, 2), (2, 3)], ...]
I tried using itertools.combinations
and itertools.permutations
but it doesn’t seem to do the job, for example the following path:
[(2,1),(1,1),(1,0),(2,0)]
does not appear on the list.
This particular function doesn’t necessarily have to output ‘valid’ paths (valid = moving one step horizontally, vertically or diagonally each time), just all of the possible combinations from the tuples representing the board. I have a function that checks if a certain path returns a valid word. I’m trying to print out all possible paths that return a valid word on the board.
Advertisement
Answer
itertools.permutations
does indeed produce all the permutations, including the [(2,1),(1,1),(1,0),(2,0)]
one that you said was missing. Note that each call to permutations
gets you all the permutations of a particular length:
>>> all_coordinates = [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3), (2, 3)] >>> from itertools import permutations >>> ((2,1),(1,1),(1,0),(2,0)) in permutations(all_coordinates, 4) True
If you want to see all the permutations from, say, length 2 to length 4, try:
for k in range(2, 5): for p in permutations(all_coordinates, k): print(p)
The resulting sequence is very long; as others have pointed out, you might want to come up with another method for generating paths that only include adjacent coordinates (e.g. a breadth-first search).
(edit) Just for fun, here’s a very quick DFS approach to building all the paths up to length 4 by looking only at adjacent coordinates:
>>> def print_paths(path): ... print(path) ... if len(path) >= 4: ... return ... x, y = path[-1] ... for dx in range(-1, 2): ... for dy in range(-1, 2): ... c = x + dx, y + dy ... if c not in path and c in all_coordinates: ... print_paths(path + [c]) ... >>> print_paths([(2, 1)]) [(2, 1)] [(2, 1), (1, 0)] [(2, 1), (1, 0), (0, 0)] [(2, 1), (1, 0), (0, 0), (0, 1)] [(2, 1), (1, 0), (0, 0), (1, 1)] [(2, 1), (1, 0), (0, 1)] [(2, 1), (1, 0), (0, 1), (0, 0)] [(2, 1), (1, 0), (0, 1), (0, 2)] [(2, 1), (1, 0), (0, 1), (1, 1)] [(2, 1), (1, 0), (0, 1), (1, 2)] [(2, 1), (1, 0), (1, 1)] [(2, 1), (1, 0), (1, 1), (0, 0)] [(2, 1), (1, 0), (1, 1), (0, 1)] [(2, 1), (1, 0), (1, 1), (0, 2)] [(2, 1), (1, 0), (1, 1), (1, 2)] [(2, 1), (1, 0), (1, 1), (2, 0)] [(2, 1), (1, 0), (1, 1), (2, 2)] [(2, 1), (1, 0), (2, 0)] [(2, 1), (1, 0), (2, 0), (1, 1)] [(2, 1), (1, 1)] [(2, 1), (1, 1), (0, 0)] [(2, 1), (1, 1), (0, 0), (0, 1)] [(2, 1), (1, 1), (0, 0), (1, 0)] [(2, 1), (1, 1), (0, 1)] [(2, 1), (1, 1), (0, 1), (0, 0)] [(2, 1), (1, 1), (0, 1), (0, 2)] [(2, 1), (1, 1), (0, 1), (1, 0)] [(2, 1), (1, 1), (0, 1), (1, 2)] [(2, 1), (1, 1), (0, 2)] [(2, 1), (1, 1), (0, 2), (0, 1)] [(2, 1), (1, 1), (0, 2), (0, 3)] [(2, 1), (1, 1), (0, 2), (1, 2)] [(2, 1), (1, 1), (0, 2), (1, 3)] [(2, 1), (1, 1), (1, 0)] [(2, 1), (1, 1), (1, 0), (0, 0)] [(2, 1), (1, 1), (1, 0), (0, 1)] [(2, 1), (1, 1), (1, 0), (2, 0)] (...)