Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 7
А нельзя было воспользоваться рекурсивной формулой для алгоритма?
А еще, зачем вам нужна была восстановимость изначальной сбалансированной после превращения ее в правильную? Для анализа распределения вероятности?
Function PlaceRand(begin, end) {
// выход из рекурсии
if (begin == end)
return
// выбираем место для скобки, закрывающей первую
opening = begin
closing = Random(begin + 1, end)
array[opening] = `(`
array[closing] = `)`
// запускаем отдельно для того, что внутри скобок, и того, что снаружи
PlaceRand(opening + 1, closing - 1)
PlaceRand(closing + 1, end)
}
PlaceRand(1, 2n)А еще, зачем вам нужна была восстановимость изначальной сбалансированной после превращения ее в правильную? Для анализа распределения вероятности?
Нет, равномерно так не получится. Возьмем n = 3. После первого запуска скобки могут быть трех типов
Каждый из типов выбирается с равной вероятностью. Нехорошо.
Да, все это нужно для анализа. Мы хотим построить взаимно-однозначное отображение между всеми сбалансированными скобками с дефектом k и правильными. Чтобы показать, что отображение взаимо-однозначное, нужно показать его обратимость.
В конечном итоге, мы как бы хотим раскидать все сбаласированные скобки по правильным, и чтобы получилось равномерно.
()****: 2 штуки.(**)**: 1 штука.(****): 2 штуки.Каждый из типов выбирается с равной вероятностью. Нехорошо.
Да, все это нужно для анализа. Мы хотим построить взаимно-однозначное отображение между всеми сбалансированными скобками с дефектом k и правильными. Чтобы показать, что отображение взаимо-однозначное, нужно показать его обратимость.
В конечном итоге, мы как бы хотим раскидать все сбаласированные скобки по правильным, и чтобы получилось равномерно.
Предыдущий комментарий был по поводу исходника.
Формулу использовать можно, но если генерировать большие последовательности, хочется избежать проблем с переполнением стека. Поэтому я развернул рекурсию.
Формулу использовать можно, но если генерировать большие последовательности, хочется избежать проблем с переполнением стека. Поэтому я развернул рекурсию.
Где же пример из 100500 скобок?
Угощайтесь =)
pastebin.com/t4CDF91v
pastebin.com/t4CDF91v
Это же можно использовать для генерации случайных бинарных функций например (Я писал генератор, но правда совсем простой, с заданными вероятностями появления определенных функций, глубиной дерева и с мультинарными деревьями для своего проекта по обработке математических выражений).
Можно ли ваш алгоритм обобщить на генерацию деревьев с произвольным количеством узлов?
Можно ли ваш алгоритм обобщить на генерацию деревьев с произвольным количеством узлов?
Да, можно. Все зависит от того, какое распределение требуется.
Вопрос я не очень понял. У меня в конце поста есть идея, как из скобочной последовательности получить дерево произвольной арности из n + 1 вершины и бинарное дерево из n вершин. Распределение и там, и там равномерное. Значение n можно выбрать любое.
Вопрос я не очень понял. У меня в конце поста есть идея, как из скобочной последовательности получить дерево произвольной арности из n + 1 вершины и бинарное дерево из n вершин. Распределение и там, и там равномерное. Значение n можно выбрать любое.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как генерировать случайные скобочные последовательности