#algo #article

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

Про это есть Sattolo's algorithm, про который пишет небезызвестный Dan Luu. Он рассказывает не только о самом алгоритме, но и о том, почему он достигает поставленной цели — и при этом не предполагает наличия знаний по комбинаторике (как про это рассказывают в других источниках). Как ни странно, алгоритм Саттоло является минимальной модификацией алгоритма Фишера-Йетса — алгоритма для построения случайной перестановки.

#prog #algo

Абсолютно контринтуитивная вещь, потому что префиксные суммы выглядят как что-то, что априори можно посчитать только последовательно

#algo

Исторические новости, однако.

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

#prog #amazingopensource #article (и даже в какой-то мере #algo)

Stacktower.io (репозиторий) — инструмент для создания визуализаций зависимостей в духе известного комикса xkcd + история о его создании, с инкрементальным улучшением, начиная с брутфорса. История хорошо демонстрирует, насколько хорошо помогает знать prior art в computer science.