Исключение лишних комбинаций

@bomber666 · Регистрация: 20.07.2021

Студворк — интернет-сервис помощи студентам

С наступающим, форумчане!

Данный код нашел на сайте, но нужно его доработать. Сам понемногу осваиваю питон, си++ для меня просто темный лес. Посидев пару дней над кодом своими силам так и не смог добиться результата, поэтому и решил попросить помощи тут.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int k = 0;
 
//may the Force be with you
void brute_print(string& s, const string& alphabet, int depth)
{
    if (depth == 0)
    {
        for (unsigned int i = 0; i < alphabet.length(); i++)
        {
            k++;
            s[s.length() - depth - 1] = alphabet[i];  //s.length() - depth - 1 можно заменить на depth, но будет другой порядок
            cout << s << endl;
        }
 
        return;
    }
 
    for (unsigned int i = 0; i < alphabet.length(); i++)
    {
        s[s.length() - depth - 1] = alphabet[i];   //s.length() - depth - 1 можно заменить на depth, но будет другой порядок
        brute_print(s, alphabet, depth - 1);
    }
}
 
int main()
{
    string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    string alphabet = "AB";
    brute_print(s, alphabet, s.length() - 1);
    cout << "k = " << k << endl;
 
    return 0;
}

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

C++
1
if (s.find("BB") == -1))

В итоге все равно перебираются все комбинации, как и в обычном случае.
Если есть вариант, кто реально понимает,как это реализовать, прошу у вас помощи!

P.S.: Предвкушая вопросы типа "А почему не оставить все это для работы питону?" отвечу - просто любой знает, что в нем скорость обработки оставляет желать лучшего, в связи с чем и начал глядеть в сторону с++

@Welemir1 · 29.12.2021, 12:29

Сообщение от bomber666

в нем скорость обработки оставляет желать лучшего,

это по каким данным и кто любой? я видел замеры что по работе со строками и регулярками питон как раз очень хорош.

Но даже если с++, к питонистам в ветке питона какой вопрос?

@bomber666 · 30.12.2021, 05:16 **[ТС]**

Тысяча извинений, перепутал ветки. Попрошу админа закрыть данную тему.
По поводу скорости, на собственном опыте убедился, что в определенной сфере, с которой я чаще всего сталкиваюсь, компилируемый код куда шустрее, чем у питона. Хотя питон в плане написания кода гораздо проще

@bomber666 · 30.12.2021, 05:31 **[ТС]**

С наступающим, форумчане!

Данный код нашел на сайте, но нужно его доработать. Сам понемногу осваиваю питон, си++ для меня просто темный лес. Посидев пару дней над кодом своими силам так и не смог добиться результата, поэтому и решил попросить помощи тут.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int k = 0;
 
//may the Force be with you
void brute_print(string& s, const string& alphabet, int depth)
{
    if (depth == 0)
    {
        for (unsigned int i = 0; i < alphabet.length(); i++)
        {
            k++;
            s[s.length() - depth - 1] = alphabet[i];  //s.length() - depth - 1 можно заменить на depth, но будет другой порядок
            cout << s << endl;
        }
 
        return;
    }
 
    for (unsigned int i = 0; i < alphabet.length(); i++)
    {
        s[s.length() - depth - 1] = alphabet[i];   //s.length() - depth - 1 можно заменить на depth, но будет другой порядок
        brute_print(s, alphabet, depth - 1);
    }
}
 
int main()
{
    string s = "aaaaaaaaaaaaaaaa";
    string alphabet = "AB";
    brute_print(s, alphabet, s.length() - 1);
    cout << "k = " << k << endl;
 
    return 0;
}

Суть программы в том, что она перебирает все возможные комбинации в строке.
В моем случае нужно исключить такие варианты, где повторяются символы, например "ВВВ" и "ВВ", которые появляются при генерации друг за другом
Попытался позаимствовать вариант из питона типа

C++
1
if (s.find("BB") == -1)

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

@alexu_007 · 30.12.2021, 09:00

У тебя строка состоит из одной буквы "а" - какие тут могут быть комбинации? И при чём тут "АВ"? Что конкретно нужно то?

@bomber666 · 30.12.2021, 12:04 **[ТС]**

Нет, строка в которой одни буквы "а" как раз отвечает за количество символов, которые нужно перебрать. "АВ" - это символы, которые участвуют в переборе. Если вы сами ее запустите, все вопросы отпадут сами собой)
Нужно сделать так, чтобы символы не повторялись по 2 и более раз для букв "А", например.
Т.е. ВВАВВВАВАВ....
А у меня получается ВВАААВВВААВАА...

@lemegeton · 30.12.2021, 15:20

Сообщение от bomber666

более раз для букв "А", например

Для какой-то одной буквы на выбор или для любых букв?

Как бы вы это на питоне написали?

Добавлено через 14 минут
Если решать "влоб", то эти значения можно просто не выводить.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
 
template<typename Visitor>
void brute_visit(std::string &s, const std::string &alphabet, int depth, Visitor visitor) {
    if (depth == 0) {
        for (char i : alphabet) {
            s[s.length() - depth - 1] = i;
            visitor(s);
        }
        return;
    }
 
    for (char i : alphabet) {
        s[s.length() - depth - 1] = i;
        brute_visit(s, alphabet, depth - 1, visitor);
    }
}
 
template<typename Iterator>
bool has_repetitions(Iterator first, Iterator last) {
    for (; (first + 1) != last; ++first) {
        if (*first == *(first + 1)) {
            return true;
        }
    }
    return false;
}
 
int main() {
    std::string initial = "aaa";
    std::string alphabet = "abc";
    for (int i = initial.length(); i > 0; i--) {
        int k = 0;
        std::string s = initial.substr(0, i);
        brute_visit(s, alphabet, s.length() - 1,
                    [&k](const auto &n) {
                        if (!has_repetitions(n.begin(), n.end())) {
                            std::cout << n << std::endl;
                            ++k;
                        }
                    });
        std::cout << "\nk = " << k << std::endl << std::endl;
    }
 
    return 0;
}

Не-влоб, надо поменять алгоритм и проверять, что изменение значений не генерирует повторения.

@bomber666 · 30.12.2021, 20:33 **[ТС]**

Сообщение от lemegeton

Для какой-то одной буквы на выбор или для любых букв?

Для определенной буквы, не для всех.

Ваш код гляну, может как раз это то, что необходимо. Спасибо!

Добавлено через 25 минут

Сообщение от lemegeton

Как бы вы это на питоне написали?

Вот так:

Python
1
2
3
4
5
from itertools import product
for i in product('AB', repeat=20):
    S = ''.join(i)
    if S.find('BB') == -1:
        print(S)

Как видите, код минимален)

@lemegeton · 31.12.2021, 07:42

Ну то есть вы генерируете весь набор, а потом отбраковываете ненужное.
Типа такого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
 
template<typename Visitor>
void brute_visit(std::string &s, const std::string &alphabet, int depth, Visitor visitor) {
    if (depth == 0) {
        for (char i : alphabet) {
            s[s.length() - depth - 1] = i;
            visitor(s);
        }
        return;
    }
 
    for (char i : alphabet) {
        s[s.length() - depth - 1] = i;
        brute_visit(s, alphabet, depth - 1, visitor);
    }
}
 
template<typename Iterator>
bool has_repetitions(Iterator first, Iterator last, char c) {
    for (; (first + 1) != last; ++first) {
        if (*first == c && *first == *(first + 1)) {
            return true;
        }
    }
    return false;
}
 
int main() {
    std::string initial = "aaa";
    std::string alphabet = "abc";
    for (int i = initial.length(); i > 0; i--) {
        int k = 0;
        std::string s = initial.substr(0, i);
        brute_visit(s, alphabet, s.length() - 1,
                    [&k](const auto &n) {
                        if (!has_repetitions(n.begin(), n.end(), 'b')) {
                            std::cout << n << std::endl;
                            ++k;
                        }
                    });
        std::cout << "\nk = " << k << std::endl << std::endl;
    }
 
    return 0;
}

@bomber666 · 01.01.2022, 23:53 **[ТС]**

Отлично! Именно то,что нужно! Хотя, первый вариант также по своему интересен.

Новые блоги и статьи Все статьи Все блоги /
Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .

@bomber666 1 / 1 / 0 Регистрация: 20.07.2021 Сообщений: 19
	30.12.2021, 05:16 [ТС]
	Тысяча извинений, перепутал ветки. Попрошу админа закрыть данную тему. По поводу скорости, на собственном опыте убедился, что в определенной сфере, с которой я чаще всего сталкиваюсь, компилируемый код куда шустрее, чем у питона. Хотя питон в плане написания кода гораздо проще 0

@alexu_007 736 / 702 / 110 Регистрация: 29.05.2015 Сообщений: 4,293
	30.12.2021, 09:00
	У тебя строка состоит из одной буквы "а" - какие тут могут быть комбинации? И при чём тут "АВ"? Что конкретно нужно то? 0

@bomber666 1 / 1 / 0 Регистрация: 20.07.2021 Сообщений: 19
	30.12.2021, 12:04 [ТС]
	Нет, строка в которой одни буквы "а" как раз отвечает за количество символов, которые нужно перебрать. "АВ" - это символы, которые участвуют в переборе. Если вы сами ее запустите, все вопросы отпадут сами собой) Нужно сделать так, чтобы символы не повторялись по 2 и более раз для букв "А", например. Т.е. ВВАВВВАВАВ.... А у меня получается ВВАААВВВААВАА... 0

@bomber666 1 / 1 / 0 Регистрация: 20.07.2021 Сообщений: 19
	01.01.2022, 23:53 [ТС]
	Отлично! Именно то,что нужно! Хотя, первый вариант также по своему интересен. 0

Исключение лишних комбинаций

Решение