CODEWITHSUNDEEP
pythonalgorithmtraveling-salesman
AndW
AndW

Reputation: 846

Algorithm to generate routes subject to pickup/delivery

Suppose we have 3 people wanting to go from point p1 to d1, p2 to d2, and p3 to d3.

I want to list all possible trips that these people could take, such that every point p1...p3, d1...d3 is on the trip, and that it satisfies pickup delivery constraint: that is, the delivery (d) for a respective number must come AFTER the pickup for that same number. For instance, p1d1 is acceptable, but d1p1 is not.

I was able to generate possible trips for 2 people, as there were only 6. But for higher numbers, it gets cumbersome. Is there an algorithm that can generate such trips?

The language in practice is python, so if there any available libraries or some such that would be helpful!

Upvotes: 0

Views: 165

Answers (1)

trincot
trincot

Reputation: 350147

This is a topological ordering problem on the directed graph defined by the edges (p1, d1), (p2, d2), (p3, d3)... where you want to collect all possible topological orderings.

There's probably some smart use possible of itertools, but here is a barebones recursive implementation:

def iterpaths(paths):
    def recur():
        if not paths:
            yield []
            return
        for i in range(len(paths)):
            val = paths[i].pop()
            if not paths[i]:
                paths.pop(i)
                for result in recur():
                    yield result + [val]
                paths.insert(i, [val])
            else:
                for result in recur():
                    yield result + [val]
                paths[i].append(val)

    yield from recur()

A run on 3 pairs:

for path in iterpaths([[1,2],[3,4],[5,6]]):
    print(path)

Upvotes: 2

Related Questions