Pull to refresh

Comments 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. После первого запуска скобки могут быть трех типов
()****: 2 штуки.
(**)**: 1 штука.
(****): 2 штуки.
Каждый из типов выбирается с равной вероятностью. Нехорошо.

Да, все это нужно для анализа. Мы хотим построить взаимно-однозначное отображение между всеми сбалансированными скобками с дефектом k и правильными. Чтобы показать, что отображение взаимо-однозначное, нужно показать его обратимость.

В конечном итоге, мы как бы хотим раскидать все сбаласированные скобки по правильным, и чтобы получилось равномерно.
Предыдущий комментарий был по поводу исходника.
Формулу использовать можно, но если генерировать большие последовательности, хочется избежать проблем с переполнением стека. Поэтому я развернул рекурсию.
Это же можно использовать для генерации случайных бинарных функций например (Я писал генератор, но правда совсем простой, с заданными вероятностями появления определенных функций, глубиной дерева и с мультинарными деревьями для своего проекта по обработке математических выражений).

Можно ли ваш алгоритм обобщить на генерацию деревьев с произвольным количеством узлов?
Да, можно. Все зависит от того, какое распределение требуется.

Вопрос я не очень понял. У меня в конце поста есть идея, как из скобочной последовательности получить дерево произвольной арности из n + 1 вершины и бинарное дерево из n вершин. Распределение и там, и там равномерное. Значение n можно выбрать любое.

Only those users with full accounts are able to leave comments. Log in, please.