Код тасовки
Сервер карточной игры тасует колоду из n карт алгоритмом Фишера — Йетса. Карты лежат на местах 1, 2, …, n, вначале на месте k — карта k. Потом для i = n, n − 1, …, 2 генератор выдаёт число ji от 1 до i, и карты на местах i и ji меняются местами (если ji = i, ничего не происходит).
Аудитор хочет проверить генератор, но в журнале сервера записан только порядок колоды после тасовки. Восстановите числа, которые выдал генератор. Они определяются колодой однозначно — на этом и держится честность алгоритма.
Вход
В первой строке n (1 ≤ n ≤ 105). Во второй — n различных чисел от 1 до n: какая карта оказалась на месте 1, на месте 2 и так далее.
Выход
В одной строке через пробел n − 1 чисел: jn, jn−1, …, j2. При n = 1 — пустая строка.
Примеры
Пример 1
5 3 5 1 4 2
2 4 1 2
Пример 2
4 1 2 3 4
4 3 2
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Какие места меняются после шага i? Что можно сказать о карте на месте i в итоговой колоде?
2Подсказка 2
Шаг i ставит на место i карту, которая лежала на месте ji. Значит, ji — это где лежала нужная карта перед шагом i. Но карты к этому моменту уже переложены предыдущими шагами.
3Идея
После шага i место i больше не трогают: следующие шаги меняют только места с номерами меньше i. Поэтому итоговая карта на месте i — та, что попала туда на шаге i. Повторим тасовку с отсортированной колоды и на каждом шаге найдём, где сейчас лежит карта, которая должна оказаться на месте i: её место и есть ji. Чтобы искать мгновенно, храним обратный массив «карта → место» и обновляем его при каждом обмене.
4Разбор
В первом примере итоговая колода 3 5 1 4 2. Шаг 5: на место 5 должна встать карта 2, она лежит на месте 2 — значит, j5 = 2; меняем, колода 1 5 3 4 2. Шаг 4: карта 4 на месте 4 — j4 = 4, ничего не меняется. Шаг 3: карта 1 на месте 1 — j3 = 1; колода 3 5 1 4 2. Шаг 2: карта 5 на месте 2 — j2 = 2. Ответ: 2 4 1 2.
Решение доказывает, что числа определяются колодой однозначно: каждый ji вычислен, а не угадан. Обратно, любые числа с 1 ≤ ji ≤ i дают какую-то колоду. Выходит, наборов чисел столько же, сколько колод: n·(n − 1)·…·2 = n!, и между ними взаимно однозначное соответствие. Если генератор выдаёт все наборы равновероятно, все n! колод тоже равновероятны — это и есть доказательство честности Фишера — Йетса из статьи. Такая запись перестановки набором чисел известна как факториальная система счисления: ji − 1 — «цифра» с основанием i.
4+Решение
5Сложность
O(n) времени и памяти: по одному обмену и одному обращению к обратному массиву на шаг.
6Типичные ошибки
- Взять исходное место карты. Карта c вначале лежит на месте c, но предыдущие шаги её уже передвинули. Ответ «итоговая карта на месте i» неверен уже в первом примере.
- Искать карту перебором.
deck.index(card)на каждом шаге — O(n2), на ста тысячах карт это миллиарды сравнений. Нужен обратный массив. - Забыть обновить обратный массив. После обмена меняются места двух карт, и обе нужно записать.