Chapter 9We can create a simple grid that shows how well a given agent is able to perform a
given task. For a small problem of a half-dozen agents and tasks, there will be a grid
of 36 costs. Each cell in the grid shows agents 0 to 5 performing tasks A to F.
We can easily enumerate all the possible permutations. However, this approach
doesn't scale well. 10! is 3,628,800. We can see this sequence of 3 million items with
the list(permutations(range(10))) method.
We would expect to solve a problem of this size in a few seconds. If we double the size
of the problem to 20!, we would have a bit of a scalability problem: there would be
2,432,902,008,176,640,000 permutations. If it takes about 0.56 seconds to generate 10!
permutations, then to generate 20! permutations, it would take about 12,000 years.
Assume that we have a cost matrix with 36 values that show the costs of six agents
and six tasks. We can formulate the problem as follows:
perms = permutations(range(6)))))
alt= [(([(sum(cost[x][y] for y, x in enumerate(perm)), perm) for perm
in perms]
m = min(alt)[0]
print([[([ans for s, ans in alt if s == m]))])
We've created all permutations of tasks for our six agents. We've computed the sums
of all the costs in our cost matrix for each task assigned to each agent. The minimum
cost is the optimal solution. In many cases, there might be multiple optimal
solutions; we'll locate all of them.
For small text-book examples, this is very fast. For larger examples, an
approximation algorithm is more appropriate.
Generating all combinations
The itertools module also supports computing all combinations of a set of values.
When looking at combinations, the order doesn't matter, so there are far fewer
combinations than permutations. The number of combinations is often stated as
()p!
r!!p
r pr=
−. This is the number of ways that we can take combinations of r things^
at a time from a universe of p items overall.
For example, there are 2,598,960 5-card poker hands. We can actually enumerate all 2
million hands by executing the following command:
hands = list(combinations(tuple(product(range(13), '♠♥♦♣')), 5))