How Many Cars Will Get Stuck In Traffic?

Problem

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

For example, if the car in the very front happens to be slowest, there will be exactly one group — everybody will eventually pile up behind the slowpoke. If the cars happen to end up in order, fastest to slowest, there will be N groups — no car ever gets stuck behind a slower car.

Solution

from itertools import permutations

def groups(perm):
    groups = 1
    min_speed = perm[0]
    for i in range(1, len(perm)):
        if perm[i] < min_speed:
            groups += 1
            min_speed = perm[i]
    return groups

runs = 11
for n in range(2, runs):
    cnt = 0
    total_groups = 0
    for p in permutations(range(n)):
        total_groups += groups(p)
        cnt += 1
    print(total_groups/cnt)