Вечерний матан

sevabashirov — 20.10.2023 Бесполезный навык номер какой-то: умею сортировать 10 попарно неравных чисел не более чем за 22 парных сравнения. То есть, например, восстановить загаданный порядок 10 элементов, задав максимум 22 вопроса о том, какой из двух правее.

(Почти) кстати: количество возможных порядков N чисел равно N! (факториал N), это общеизвестно, а вот количество конфигураций, если возможны равенства - упорядоченные числа Белла; они же соответствуют количеству конфигураций без равенств, но с допустимостью неполной информации, то есть когда все N чисел разбиваются любыми способами на группы, внутри каждой из которых установлен порядок (группы могут быть и единичными). А вот если одновременно допустимы и равные числа, и неполнота информации - то и такое уже есть в Симпсонах OEIS: https://oeis.org/A075729, фактически это количество разных заполнений бюллетеня преференциального голосования.

На этом месте могла быть таблица о том, сколько бит информации всё это занимает, но посчитать в уме двоичный логарифм каждый уважающий себя читатель должен уметь. Принимаю донаты на починку сарказмометра.

Оставить комментарий

Популярные посты:

• Ранее
• Архив