Как да генерирам произволни последователности на скоби

Когато тествам алгоритми, често имам задачата да генерирам произволно двоично дърво. Освен това списъкът с желания не се свежда до произволно дърво, а се взема от еднакво разпределение. Въпреки привидната простота, ефективното изграждане на такова дърво съвсем не е тривиално.

Заглавието на тази статия съдържа думите "последователност от скоби". Има нещо повече зад тези думи, тъй като скобите могат да се използват за описание на голямо разнообразие от обекти, включително двоични дървета. На този факт беше посветена отделна публикация за Хабре.

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

На даден н генерирайте правилна последователност в скоби според равномерното разпределение по всички правилни последователности с дължина 2н.

Известно е, че броят на редовните скоби с дължина 2н се равнява н-ият номер на каталунски. За изчисляване на каталонските числа има изрични

и рекурсивно

формули.

Нуждаем се от генератор на произволни числа. На даден н, ще генерира еднакво вероятно случайно число между 0 и. Също така се нуждаем от генератор на случайни пермутации върху списъци. В python се нарича random.shuffle. За нас ще бъде достатъчно, че работи линейно и по последователността 1,2. н генерира произволна пермутация според еднакво разпределение.

Три начина да кажете „Може би“

Силите на динамичното програмиране

Има идея, че всички правилни последователности в скоби могат да бъдат номерирани. И, например, ето подробно описание на това как да направите това. Така че, можете да приложите такъв план.

Разглеждаме n-тото каталонско число.
Генерираме произволно число от 1 до .
Използвайки динамично програмиране и комбинаторно броене, възстановяваме скобата последователност по нейния номер.

Планът е почти перфектен. Тези. планът е доста добър, ако н - малък, по-малък от 30. Но ако n се окаже от порядъка на 1 000, ще е необходима дълга аритметика, алгоритмите чрез препратка вместо обещания квадрат ще работят кубично време и като цяло динамичното програмиране не е бъркотия за теб. Мисля, че ще е необходима много работа, за да се изпълни такъв план поне през. Нека потърсим алтернативни начини.

Опитайте и проверете

Нека да разгледаме отново изричната формула за каталонски числа.
.
Всъщност това означава, че има много правилни последователности в скоби.

Ще извикаме последователността балансиран, ако броят на отварящите и затварящите скоби е еднакъв. Например последователностите ") (()", "() ()" са балансирани, но последователността "()))" не. Очевидно е, че всяка правилна последователност е балансирана. Общо от всички възможни балансирани последователности на дължината 2н съществуват. Ако една от тези последователности е избрана на случаен принцип, тогава тя се оказва вярна с вероятност

Генерирайте произволна балансирана скоба в съответствие с еднаквото разпределение.
Проверяваме го за коректност.
Ако последователността е правилна, тогава изведете. Ако не, тогава се връщаме към точка 1.

Нека започнем с първата точка: как да генерираме такава произволна последователност в скоби. Да вземем произволна балансирана последователност и да я разбъркаме чрез random.shuffle.

Ако седите с лист хартия и химикал, можете да го разберете за всяка балансирана скоба х има точно пермутации, които вземат произволна начална балансирана последователност х. Това означава, че random.shuffle генерира всяка балансирана последователност с еднаква вероятност. Получаваме алгоритъма.