Известная задача с потерянным билетом: реализация на Python

Пора браться за код! Разбираем решение популярной задачи на Python. Как бонус, сравнение скорости реализации с алгоритмом на R.

100 человек садятся на самолёт. Каждому из них предназначается единственное место, согласно билету. Первый пассажир потерял билет, поэтому не знает положенного номера. Он занимает случайное сиденье на борту. Остальные люди садятся на указанные места или выбирают произвольное свободное кресло, если их заняли. Какова вероятность того, что последний человек будет в кресле, согласно билету?

Этот вопрос подкинула подруга, технический помощник на вводном курсе по математике для биологов в Университете Мэриленда. Профессор предложил задачу классу для решения на семинаре. Студенты, как один, уверяли, что ответ – 50%: последний на борту либо получает нужное место, либо нет. По этой логике предлагаю купить лотерейные билеты, потому что у каждого шанс выиграть 50%.

Я чувствовал, что это излишне громоздкая задача, чтобы идти напрямую и вычислять вероятность каждого отдельного варианта. Хотя доступны аналитические решения, предположил, что справлюсь с помощью симуляции. Я – Python разработчик, поэтому выбор языка очевиден.

Реализация на Python

Вот ряд шагов для выполнения:

1. Создайте «самолёт» (массив) из 100 «мест».
2. Составьте схему рассадки: в произвольном порядке присвойте каждому человеку кресло.
3. Случайным образом назначьте первую персону на место.
4. Посадите на борт остальную часть самолёта, где каждый человек займёт назначенное сиденье или случайное, свободное.
5. Посчитайте, получил ли последний пассажир на борту отведённое кресло.
6. Повторите шаги 1–5 кучу раз.
7. Найдите вероятность того, что последний человек получит нужное место.

Первые шаги

Начальная функция симуляции выглядела так:

def airplane_sim(sims=100, n=10):
    lggas = 0 # последний получает указанное место
    for j in range(sims):
        passengers = np.arange(n)
        assigned_seats = np.arange(n)
        np.random.shuffle(assigned_seats)
        taken_seats = np.zeros(n)
        for i in passengers:
            if i == 0:
                taken_seats[np.random.randint(0, n)] = 1
            elif i == n - 1:
                if taken_seats[assigned_seats[i]] == 0: 
                    lggas += 1
            else:
                taken_seats = assign_seat(taken_seats, assigned_seats[i])
    return(lggas / sims)

def assign_seat(seating_chart, assigned_seat):
    open_seats = [i for i, q in enumerate(seating_chart) if q == 0]
    if assigned_seat in open_seats: seating_chart[assigned_seat] = 1
    else: 
        randomly_assigned_seat = open_seats[np.random.randint(0, len(open_seats))]
        seating_chart[randomly_assigned_seat] = 1
    return seating_chart

Неприглядно, но работоспособно. Мы строим очереди пассажиров, назначаем места и медленно заполняем самолёт. Рабочая лошадка – функция assign_seat, которая принимает схему посадки и позицию пассажира. И впоследствии определяет, где этот человек будет сидеть. Как доберётесь до последнего участника, проверьте занятость его кресла. Если свободно, увеличьте lggas (завершающий пассажир получает назначенное место). Хотя логически способ выполняет необходимое и даёт правильное решение проблемы, он неподобающе медленный и громоздкий.

Изменения

Начинали с присвоения случайным образом сидений пассажирам. Улучшим этот алгоритм путём допущения, без потери общности, что каждому назначается место последовательно. (Человек 1 на сиденье 1, пассажир 2 на 2) Так устраним перетасовку и постоянный поиск нужного места. С этим упрощением проблемы также отпадает необходимость в массиве назначенных позиций, что экономит пространство памяти.

Затем я работал над удалением списка присвоенных посадочных мест и пришёл к функции airplane_sim2:

def airplane_sim2(n_passengers=100):
    x = np.arange(n_passengers)
    x[0] = np.random.randint(n_passengers)
    for p in range(1, n_passengers):
        if p in x[:p]:
            x[p] = np.random.randint(p+1, n_passengers+1) % n_passengers
    lggas = x[n_passengers - 1].astype(bool).sum()
    return lggas

Запустите второе решение и сравните время выполнения с первым, и заметите ускорение. А также при достаточном повторении получите ответ на задачу (подробнее об этом через секунду). Во втором случае единственный массив – места, где сидят люди.

Предполагаем, что j-й пассажир попадает на кресло j. И назначаем первому человеку произвольное место. Затем для каждого проверяем занятость отведённой ему позиции (строка 5). Если это так, то человеку присваиваем произвольное сиденье в самолёте позади других или место 0 (строка 6). Потому что предыдущие кресла, кроме 0, пассажиры займут при посадке на борт, а сиденье 0 принадлежит первому участнику. Случайное распределение мест появляется, когда кресло 0 пустое. Последняя строка – хак, который я придумал в попытках векторизовать процесс. (Выглядело круто, поэтому добавил его во все решения.) Исходя из формулировки задачи, последний в самолёте получает либо установленное место (99), либо предназначенное первому участнику (0). Поэтому преобразуйте значение в boolean и просуммируйте строки, чтобы рассчитать количество раз, когда последний человек получил положенное место. Это не нужно при симуляции с единственным самолётом, но получаем любопытный способ подсчёта ненулевых элементов в ряду.

Оптимизация

Симуляция показывает, как решение принимает очертания. Посмотрите на место последнего: этот человек получает либо кресло по билету, либо назначенное первому участнику. Чтобы определить, сядет ли последний человек, куда нужно, проверим занятость места 0. Когда позиция 0 становится несвободна, остальные участники получат положенные сиденья. А также заметьте, когда первый человек занял кресло j, то каждый пассажир перед j получает требуемое место. Поэтому дополнительно оптимизируем решение: будем рассматривать тех, чьё сиденье занято. Реализация:

def airplane_sim_fast(n_passengers=100):
    x = np.arange(n_passengers)
    x[0] = np.random.randint(n_passengers)
    p = x[0].copy()
    while p:
        x[p] = np.random.randint(p+1, n_passengers+1) % n_passengers
        p = x[p].copy()
    return x[n_passengers-1].astype(bool).sum()

Сократили просмотр людей и получили замену цикла for на while. В худшем случае последний будет выполняться (n_passengers -1) раз, но наверняка реже. И до присвоения сиденья 0, и в этот момент устанавливается место последнего участника.

Альтернатива

Я натолкнулся на решение задачи на R в блоге Дэвида Робинсона. Он использовал другую стратегию произвольного распределения: человек, сиденье которого заняли, меняется позициями с последующим пассажиром. Ниже моя реализация этого алгоритма.

def airplane_sim3(n_passengers=100):
    x = np.arange(n_passengers)
    x[0] = np.random.randint(n_passengers)
    for p in range(1, n_passengers):
        if p in x[:p]:
            switch_with = random.sample(range(p, n_passengers), 1)[0]
            x[[p, switch_with]] = x[[switch_with, p]]
    lggas = x[n_passengers - 1].astype(bool).sum()
    return lggas

Робинсон также воплотил симуляцию на матрице вместо одномерного массива или вектора, что ускоряет вычисления в 20 раз. Я не написал его матричный алгоритм на Python, но сделал это для своего:

def airplane_sim4(n_passengers=100, n_planes=100):
    # Когда присваивается позиция 0, последующие пассажиры займут свои места.
    x = np.arange(n_passengers)
    y = np.repeat(x, n_planes, axis = 0)
    y = y.reshape((n_passengers, n_planes))
    y[0,:] = np.random.randint(n_passengers, size=n_planes)
    for p in range(1, n_passengers):
        q = np.where(y[:p] == p)[1]
        y[p,q] = np.random.randint(p+1, n_passengers+1, size=len(q)) % n_passengers
    lggas = y[n_passengers - 1,:].astype(bool).sum()
    return lggas / n_planes

Создаём двумерный массив (n_passengers x n_planes) для работы. Когда первый пассажир получил произвольное место, происходит магия. Для каждого человека строка 8 определяет самолёты с занятым креслом. Строка 9 затем назначает новую позицию каждому из тех, кого выгнали с указанного места (либо позади, либо на 0). (Обратите внимание, что человеку присваивается «другое» случайное сиденье, а не одинаковое во всех самолётах. Я потратил кучу времени на отладку.) Используем симпатичный хак, чтобы узнать количество раз, когда последний участник получал место согласно билету, и возвращаем эту долю времени.

Скорость

Что быстрее? Язык программирования Python или R? Моя реализация или Робинсона? Его скорости выше. ~ 2,6 мс для симуляции 1 тыс. самолётов на 100 человек с использованием его матричного решения.

Удалось воспроизвести на Python начало алгоритма Робинсона, а не весь. Поскольку получилось выполнить его симуляцию с одним самолётом, рассмотрим эти скорости.

Python библиотека timeit показывает, что мой второй вариант работает на ~ 10% быстрее, чем алгоритм Робинсона для задачи с единственным авиалайнером. А как насчёт сравнения оптимизации?

Смотрите, этот результат в 20 раз быстрее предыдущих реализаций с циклом for. Замещение на while ускорило процесс! Алгоритм также работает в 3 раза быстрее, чем у Робинсона с одним самолётом. Поскольку он наблюдал увеличение скорости в 20 раз при переходе на матрицу, круто увидеть подобный результат. Перенести на матрицу этот алгоритм не смог, но попытался:

def airplane_sim_fast_matrix(n_passengers=100, n_planes=1000):
    x = np.arange(n_passengers)
    y = np.repeat(x, n_planes, axis = 0)
    y = y.reshape((n_passengers, n_planes))
    y[0,:] = np.random.randint(n_passengers, size=n_planes)
    p = y[0,:].copy()
    while p.sum():
        for i, q in enumerate(p):
            if not q: continue
            y[q,i] = np.random.randint(q+1, n_passengers+1) % n_passengers
            p[i] = y[q,i]
    return y[n_passengers-1].astype(bool).sum()

Цикл while работает, пока присутствует самолёт, где человек не сидит на месте 0 (и дойдёт до последнего пассажира, ведь полагаем, что он получит кресло 0 в половине самолётов). Затем проходим по занятым сиденьям и случайно назначаем этому человеку место, как и в других симуляциях. Позиция хранится в памяти, причём процесс повторяется, пока не будут заняты все сиденья 0. Скорость посадки на 1 тыс. самолётов по 100 пассажиров смотрите ниже.

Хотя я не разобрался, как правильно использовать матричные операции, увеличение скорости налицо. Вопреки выполнению этого алгоритма на матрице, видим, что R-реализация Робинсона в 3 раза быстрее. Даже несмотря на то, что Python база с одним самолётом работает лучше.

Почему симуляция?

Поскольку эту задачу решают аналитически, вы спросите: «Зачем напрягаться?» Хоть симуляция не нужна специально для этой проблемы, что с другими вопросами? Спрошу: «Каково среднее количество людей, которые получили места случайным образом при посадке в самолёт?» Или «Какова дисперсия числа людей с произвольными местами?» Это легко добавить в текущий алгоритм, но требует дополнительной работы.

Симуляция станет проверкой адекватности, когда аналитическое решение под сомнением. Пример тому – Пал Эрдёш и Парадокс Монти Холла.

Эту задачу также нередко задают на собеседованиях по всему миру.

А какие интересные задачи с собеседований могли бы выделить вы?