#algorithms #math #jokes
Посвящается нашему офис-менеджеру Алине
Новогодние поздравления в Студии проходят по принципу церемонии Тайного Санты. Как же офис-менеджеру Алине организовать этот процесс, сохраняя максимальную анонимность, при условии что в Студии работает 100+ человек? 😱
Каждый сотрудник должен получить адресованный ему подарок, иначе на общем вручении выйдет конфуз.
Алина берет список всех сотрудников у HR Дарьи и садится за разработку алгоритма (идет к старшему разработчику Александру).
Чтобы организовать случайность пар «дарящий — получатель», список сотрудников перемешивается и помещается в массив
L1. Затем элементы множества L1 циклически смещаются в любую сторону на число, не равное length(L1), и записываются в новый массив L2.Теперь в
L1[i] находится отправитель подарка для получателя L2[i]. Читателю должно быть очевидно 😂, что получившееся отображение f: L1 -> L2 биективно, а потому подарки достанутся всем. 🎁Пары получены, но наша Алина делала все вручную, и теперь она знает все «тайны» и, что самое обидное, знает, кто подарит подарок именно ей. Исправим это с помощью HR Дарьи.
Даша и Алина делят список
L1 на L11 и L12 таким образом, что Даша находится в одном списке, а Алина — в другом. Каждая из девочек выбирает себе половину списка, в котором нет ее фамилии/имени. Повторим процедуру перемешивания и сдвижки для списков L1j, сохраняя список со сдвигом в L2j. Теперь в L1j[i] находится отправитель подарка для L2j[i], где j = 1,2. Очевидно, что полученные отображения f1j: L1j -> L2j также биективны. Все учтено при полной секретности. 😎З.Ы. Реализацию алгоритма оставим на усмотрение любопытного читателя. С наступающим Новым годом и Рождеством! 🎄