Pull to refresh

Как генерировать случайные скобочные последовательности

Algorithms *
Привет, Хабр!

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

В названии этой статьи присутствуют слова «скобочная последовательность». За этими словами скрывается нечто большее, поскольку с помощью скобок можно описать очень разнообразные объекты, в том числе и бинарные деревья. На Хабре этому факту был посвящен отдельный пост.

В этой статье я расскажу несколько способов генерирования случайной скобочной последовательности, в том числе за линейное время, а потом приведу пример преобразования последовательности в бинарное дерево. Интересно?

Добро пожаловать под кат
Total votes 37: ↑35 and ↓2 +33
Views 19K
Comments 7

Как посчитать перестановки. Лекция в Яндексе

Яндекс corporate blog Abnormal programming *Algorithms *Mathematics *
Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



Под катом — подробная текстовая расшифровка и большинство слайдов.
Total votes 57: ↑57 and ↓0 +57
Views 25K
Comments 12

Короткое плечо совпадения

Mathematics *
Translation
Джеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:

Tweet reads: 4!+1 = 25, a square number. 5!+1 = 121, a square number. Another example? Two more examples?

«4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»

С помощью ручки и бумаги легко показать, что $6!$ не подходит. Факториал $6!$ — это $1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$; прибавив $1$, получим число $721$, которое не является квадратом. (Оно раскладывается на множители как $7 \times 103$.) С другой стороны, $7!$ равно $5040$, а прибавив $1$, мы получим $5041$, что равно $71^2$. Это даёт нам очень милое уравнение:
Читать дальше →
Total votes 41: ↑39 and ↓2 +37
Views 16K
Comments 26