Генерация случайной строки со сбалансированными скобками

#c #алгоритм #генерация_случайных_данных

Возникла тут проблемка генерить случайную строку со сбалансированными скобками.
Т.е. строка abc(def(g)h)i - сбалансирована, а abc(def(g)hi и abc)(def)g - нет. Код
есть, и он работает нормально но есть одна проблемка: почти все строки заканчиваются
закрывающими скодками. Где я вижу проблему, и собственно вопрос - под кодом.

char * create_balanced_cstring(const char *alphabet, // строка нейтральных символов
(напр abcdefg...)
                               char obr, char cbr, // открывающая и закрывающая скобки
                               unsigned lmin, unsigned lmax) // мин и макс длина строки
{
    if (strchr(alphabet, obr) || strchr(alphabet, cbr))
        return 0;
    if (lmin > lmax || lmin == 0)
        return 0;

    int lenalph = strlen(alphabet); // длина "алфавита" нейтральных символов
    int length = rand() % (lmax - lmin + 1) + lmin; // длина генерирующейся строки
    char *s = (char*) malloc(length + 1);
    if (!s)
        return s;

    int opened = 0; // кол-во открытых скобок
    int just_opened = 0; // флаг для избегания фрагментов '()'
    char curchar; // текущий символ в строке
    for (int i = 0; i < length; ++i) {
        if (opened == length - i)
            curchar = cbr;
        else {
            if (opened + i + 2 >= length)
                curchar = alphabet[rand() % lenalph];
            else {
                int r = rand() % length;
                if (r < opened * 3 && !just_opened)
                    curchar = cbr;
                else if (r > 2 * length / 3 - opened)
                    curchar = obr;
                else
                    curchar = alphabet[rand() % lenalph];
            }
        }

        if (curchar == obr) {
            ++opened;
            just_opened = 1;
        } else {
            just_opened = 0;
            if (curchar == cbr) --opened;
        }

        s[i] = curchar;
    }
    s[length] = '\0';

    return s;
}


Проблема, ИМХО, тут:

        int r = rand() % length;
        if (r < opened * 3 && !just_opened)
            curchar = cbr;
        else if (r > length - opened)
            curchar = obr;
        else
            curchar = alphabet[rand() % lenalph];


т.е. с выбором в (условно) начале строки - открывать скобку, закрывать, или ставить
случайный символ. Хочется, чтобы вероятность открыть скобку увеличивалась, если их
открыто мало и наоборот, закрыть - увеличивалась если открыто много и наоборот. Просто
поиграться с коэффициэнтами? Текущие *3 и 2/3 - эмпирические, так вроде еще более-менее.

Т.е. в итоге нужно по 3-м параметрам (длина строки l, текущая позиция i и количество
незакрытых в этой позиции скобок o) сделать распределение вероятности выбора открывающей/закрывающей
скобки или "нейтрального" символа (не скобки) в данной позиции
    

Ответы

Ответ 1

Посмотрите Кнута, "Искусство программирования", т. 4А, стр. 511 русского издания,
алгоритм W - равномерно распределенные случайные строки вложенных скобок. Алгоритм
генерирует случайную строку корректно вложенных скобок для заданного их количества. 

Растыкать случайным образом 2n мест для скобок в строке, сгенерировать строку скобок
и вставить на подготовленные места - не подойдет?