paths.py

from copy import deepcopy

def find_paths(rows):
    if len(rows) == 1:
        return rows

    head = rows[-1]
    previous_paths = find_paths(rows[:-1])

    paths = deepcopy(previous_paths) + [head]
    return paths + [p + [head[2]] for p in previous_paths if p[-2:] == head[0:2]]

def remove_small(paths):

    for p in paths:
        others = [1 for other_p in paths if p != other_p and is_included(p, other_p)]

        if not others:
            yield p

def is_included(p, other_path):
    n = len(p)
    other_n = len(other_path)

    if other_n < n:
        return False

    for i in range(other_n - n + 1):
        if p == other_path[i:i+n]:
            return True

    return False

# -------------------------- testing ----------------------------

assert is_included([1], [1])
assert is_included([1, 2], [1, 2, 3])
assert is_included([1, 2], [0, 1, 2, 3])
assert not is_included([1, 2], [0, 1, 3, 2, 3])
assert is_included([1, 2], [0, 1, 2])

rows = [[0, 1, 0], [0, 2, 0],  [0, 3, 0],  [0, 3, 4], [0, 3, 5], [3, 4, 6], [3, 4, 8],  [3, 5, 8], [3, 5, 9], [4, 6, 0], [0, 7, 0],  [4, 8, 0], [5, 8, 9], [5, 9, 0], [8, 9, 0],]

paths = find_paths(rows)
kept_paths = list(remove_small(paths))

assert paths == [[0, 1, 0], [0, 2, 0], [0, 3, 0], [0, 3, 4], [0, 3, 5], [3, 4, 6], [0, 3, 4, 6], [3, 4, 8], [0, 3, 4, 8], [3, 5, 8], [0, 3, 5, 8], [3, 5, 9], [0, 3, 5, 9], [4, 6, 0], [3, 4, 6, 0], [0, 3, 4, 6, 0], [0, 7, 0], [4, 8, 0], [3, 4, 8, 0], [0, 3, 4, 8, 0], [5, 8, 9], [3, 5, 8, 9], [0, 3, 5, 8, 9], [5, 9, 0], [3, 5, 9, 0], [0, 3, 5, 9, 0], [8, 9, 0], [5, 8, 9, 0], [3, 5, 8, 9, 0], [0, 3, 5, 8, 9, 0]]
assert kept_paths == [[0, 1, 0], [0, 2, 0], [0, 3, 0], [0, 3, 4, 6, 0], [0, 7, 0], [0, 3, 4, 8, 0], [0, 3, 5, 9, 0], [0, 3, 5, 8, 9, 0]]