@s_hoffman

Как расчитать кол-во вариантов при рандомизации текста?

Я пытаюсь сделать простенький рандомизатор текста.

Принцип работы - стандартный.
{a|b} - установить a ИЛИ b
[c|d] - установить все элементы в рандомном порядке.
С самим рандомизатором проблем не возникло, но появился другой вопрос: Как расчитать количество уникальных комбинаций для определенного текста?

На данный момент мой код выглядит так:
import re, random

string = '{я {купил|приобрел} {на ярмарке|на рынке|в магазе} {сыр, |[соль, |хлеб, |муку, ]}сахар}'

def myshuffle(l):
    random.shuffle(l)
    return l

def RandomText(text):
    while re.search(r'\[.*\]', text):
        text = re.sub(r'\[([^\[\]]*)\]', lambda m: "".join(myshuffle(m.group(1).split('|'))), text)
    while re.search(r'{.*}', text):
        text = re.sub(r'{([^{}]*)}', lambda m: random.choice(m.group(1).split('|')), text)
        
    return text

print(RandomText(string))

>>я приобрел в магазе соль, хлеб, муку, сахар
>>я купил на рынке муку, хлеб, соль, сахар
>>я купил на ярмарке сыр, сахар


Мне удалось расчитать количество "на пальцах". Если выразить это псевоуровнением (если можно так назвать), то для данного текста получится что-то типа:
w = {купил|приобрел}
x = {на ярмарке|на рынке|в магазе}
y ={сыр, |z}
z = [соль, |хлеб, |муку, ]
len(w) * len(x) * (z! + len(y) - 1)
По идее надо посчитать это для каждого уровня вложенности и поднимаясь уровнем выше складывать результаты.
Но как выразить это в коде?

Увы я не математик..
Уверен, там есть какое-то изящьное решение для этого.

Подскажите, куда копать.
  • Вопрос задан
  • 192 просмотра
Решения вопроса 2
Vindicar
@Vindicar
RTFM!
Обозначим одну подстановку как "терм", и допустим, что все варианты в терме уникальны (т.е. нет повторений внутри одного терма).
Для терма {} количество комбинаций равно количеству вариантов в терме.
Для терма [] количество комбинаций равно количеству перестановок вариантов в терме, т.е. факториал от количества комбинаций.
Для всего выражения количество комбинаций должно быть равно произведению количеств комбинаций для каждого терма.

С вложенными вариантами чуть сложнее.
Для {} количество вариантов это по сути сумма их весов.
Для [] количество вариантов считается так: количество перестановок вариантов, умноженное на произведение весов вариантов.
У простой строки вес 1, у вложенного терма вес равен количеству его комбинаций.
Таким образом, можно посчитать число комбинаций рекурсивно.

import math

class RandomChoice(list):
    pass

class RandomOrder(list):
    pass

def random_choice(options) -> int:
    total = 0
    for option in options:
        if isinstance(option, RandomChoice):  # вложенный выбор варианта
            total += random_choice(option)
        elif isinstance(option, RandomOrder):  # вложенное переупорядочивание
            total += random_order(option)
        else:
            total += 1
    return total

def random_order(options) -> int:
    total = math.factorial(len(options))
    for option in options:
        if isinstance(option, RandomChoice):  # вложенный выбор варианта
            total *= random_choice(option)
        elif isinstance(option, RandomOrder):  # вложенное переупорядочивание
            total *= random_order(option)
        # а для просто варианта ничего делать не надо
    return total

def total_count(items) -> int:
    total = 1
    for item in items:
        if isinstance(item, RandomChoice):  # вложенный выбор варианта
            total *= random_choice(item)
        elif isinstance(item, RandomOrder):  # вложенное переупорядочивание
            total *= random_order(item)
    return total

sample = [
    'я', 
    RandomChoice(['купил', 'приобрел']), # 2
    RandomChoice(['на ярмарке','на рынке','в магазе']), # 3
    RandomChoice(['сыр', #8
        RandomOrder(['соль, ','хлеб, ','муку, ']), # 6
        'сахар']),
]


combos = total_count(sample)
print(combos)
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
Ради интереса запилил свой вариант. В нем нет ошибки, о которой говорил в комментах. Функция parse разбирает шаблонную строку в дерево, по которому можно и рандомную строку получить, и посчитать количество вариантов. Пример использования в самом низу.
Код на js, можно целиком скопипастить в консоль браузера, выполнить и посмотреть.

код

// ------- utls ----------
function getRand(n) {
    return Math.floor(Math.random() * n);
}

function fact(n) {
    let f = 1;
    for (let i = 2; i <= n; ++i) {
        f *= i;
    }
    return f;
}

function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; --i) {
        const r = getRand(i + 1);
        const t = arr[r];
        arr[r] = arr[i];
        arr[i] = t;
    }
    return arr;
}

// ------- classes ----------
class Str extends String {
    getCount() { return 1; }
}

class Line {
    arr = [];
    toString() {
        return this.arr.slice(0).join('');
    }
    getCount() {
        return this.arr.reduce((r, a) => r * a.getCount(), 1);
    }
}

class Select {
    arr = [];
    toString() {
        return this.arr[getRand(this.arr.length)].toString();
    }
    getCount() {
        return this.arr.reduce((r, a) => r + a.getCount(), 0);
    }
}

class Order extends Line {
    arr = [];
    toString() {
        return shuffle(this.arr).join('');
    }
    getCount() {
        return fact(this.arr.length) * this.arr.reduce((r, a) => r * a.getCount(), 1);
    }
}

// ------- parse ----------

function parse(str) {
    const reg = /[{}|\[\]]/g;
    let start = 0;
    let line = new Line();
    const stack = [{
        arr: [line],
    }];
    // debugger;
    while (true) {
        const match = reg.exec(str);
        if (!match) {
            if (str.length - start > 0) {
                line.arr.push(new Str(str.substring(start)));
            }
            break;
        }

        if (match.index - start > 0) {
            line.arr.push(new Str(str.substring(start, match.index)));
        }

        start = reg.lastIndex;

        const c = match[0];

        if (c === '{' || c === '[') {
            const container = c === '{' ? new Select() : new Order();
            line.arr.push(container);
            stack.push(container);
            line = new Line();
            container.arr.push(line);
        } else {
            if (stack.length < 2) {
                return null;
            }
            const container = stack[stack.length - 1];
            if (line.arr.length === 1) {
                container.arr[container.arr.length - 1] = line.arr[line.arr.length - 1];
            }
            if (c === '|') {
                line = new Line();
                container.arr.push(line);
            } else {
                stack.pop();
                const arr = stack[stack.length - 1].arr;
                line = arr[arr.length - 1];
            }
        }
    }
    return stack.length > 1 ? null : line.arr.length === 1 ? line.arr[0] : line;
}

// --------
const p = parse('{ttt|2}qqq[1|2|3{[4|q]|5}]');

console.log(p.toString());
console.log(p.getCount());
console.log(p);

Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы