All possible combinations of a list of tuples

Question

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.

Did you look at `itertools.permutations`, which is like `combinations` but with different orderings? — Samwise, Jan 01 '22 at 17:48
Does this answer your question? [How to generate all permutations of a list?](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list) — Riccardo Bucco, Jan 01 '22 at 17:49
I did try to use `itertools.permutations`, but it didn't solve my problem. I'll edit the question now. — itailitai, Jan 01 '22 at 17:50
it 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'm creating a 'Boggle' game, and 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. — itailitai, Jan 01 '22 at 17:56
I wouldn't recommend this. The number of possible orders of your tuples can be really huge. Just generate and test the valid paths. — Thierry Lathuille, Jan 01 '22 at 17:59
It will go exponentially based on a size of the path. It may quickly stop be possible to work with all these possibilities. — Maciej Czarnecki, Jan 01 '22 at 18:03
No reason, I just messed with it while trying to figure out what's wrong — itailitai, Jan 01 '22 at 18:19

Samwise · Accepted Answer · 2022-01-01T18:32:50.147

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)]
(...)

Thanks, that answers my question although it seems like I'll have to try another approach as you said. — itailitai, Jan 01 '22 at 18:18
Fun [deltaless version](https://tio.run/##XZDdCoMwDIXv@xTn0jIFq7sYA/ciIiL@MEFaqR3Yp3eNhrktFwn5Tpommb17Gp3fZrttzTTVrTG2G3Xj@gUFyiiNkcoYkeKYcQxcMVfMFfOMecY8Y54zz5nnshKi6wfMdtSunhv3XCLy8i4QbMcH2PNxwNTrA@BR4HqUkdnevaze0zWGD5NTVZmoameDsVgxaqxJ@H@9kDsfk@pJ9aR6Uv2pkrWhIfX9gWGcFto4ekm/odFdICH7u@Nvr89mXwvjgrKtpBDfQnnctJLb9gY). Your `...` are rather inconvenient btw. — Kelly Bundy, Jan 01 '22 at 18:52

All possible combinations of a list of tuples

1 Answers1