Разминка для мозгов: генерация всех возможных слов заданной длины с произвольным алфавитом

Дан алфавит:

std::vector<std::string> abc {
    "1",
    "2",
    "3",
    ....
};

Дано некое N:

std::size_t N = ... ;

Необходимо перебрать все возможные слова (комбинации) заданной длины (N),
которые можно составить с помощью заданного алфавита (abc).

Пример:
Алфавит: «1», «2».
Длина слов: 3

Результат вывода в консоль (порядок не важен):
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

Дополнительно:
1) Возможность составления букв алфавита из нескольких символов:

std::vector<std::string> abc {
    "ZZZ",
    "XX",
    "Y",
};

2) Возможность работы с большими алфавитами и длинами слов.
3) Многопоточная генерация и обработка.
4) Возможность из клиентского кода задать действие, которое будет выполняться с каждым словом.
5) Буквы алфавита могут частично или полностью совпадать.

Использовать можно стандартные библиотеки C и C++ (в т.ч. из C++17).

Так что можете тоже мозгами пораскинуть. :)

upd: исправлен алфавит

Видимо имелось ввиду std::string abc[] = { ... }; или даже const std::string abc[] = { ... };?

Я бы даже сказал std::vector<std::string>

Я так прикинул, программка получилась на ~30 строк с реализацией 1, 2, 5 из «дополнительно». Без использования STL, кроме string и vector.

С многопоточностью не заморачивался.

Пункт 4 — не понял. Что имеется ввиду?

Пункт 4 — не понял. Что имеется ввиду?

Ну у нас же идет только вывод комбинаций,
а пунтк 4 предполагает, что клиент может задать поведение,
т.е. передать в нашу функцию какой-нибудь функтор,
который будет принимать строку с текстом (комбинацию),
и как-то её обрабатывать.

Есть вот такая, глупенькая реализация: http://rextester.com/HPLG75261
Включает в себя 1, 3, 4, 5.

А вот реализация с 1, 2, 5: http://rextester.com/LZTR96135
Добавить 4 сюда не проблема.

Посмотрел код по ссылкам — жуть. Особенно вариант с потоками. Я как-то обошёлся гораздо меньшей кровью. Но мой вариант сложно перевести на многопоточную обработку. Прикрутил пункт 4.

Поскольку ты уже опубликовал ссылки на варианты решения, и интриги больше нет, выкладываю свой вариант.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> abc{ "1", "2" };

const size_t N = 3;

typedef string (*Func)(const string &s);

void gen(const vector<string> &alf, string s, size_t n, Func f) {
    for (size_t i = 0; i < alf.size(); ++i) {
        if (n > 1) {
            gen(alf, s + f(alf[i]) + " ", n - 1, f);
        }
        else {
            cout << s + f(alf[i]) << endl;
        }
    }
}

string bracket(const string& s) {
    return "[" + s + "]";
}

int main() {
    string s;
    gen(abc, s, N, bracket);
    return 0;
}

А у тебя, видимо, припасено решение в темплейтно-функциональном (привет, STL!) стиле под флагом C++17? Выкладывай. Интересно посмотреть.

А вот вариация на тему http://rextester.com/LZTR96135. Вроде даже попроще получилось.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> abc{ "1", "2", "3" };
const size_t N = 4;

// разложение числа на "цифры" по основанию системы счисления (radix)
void next_comb(long long num, size_t radix, vector<size_t> &idxs) {
    for (int i = idxs.size(); i > 0; --i) {
        idxs[i - 1] = num % radix;
        num /= radix;
    }
}

void gen2(const vector<string> &alf, size_t n) {
    size_t alf_len = alf.size();
    long long total = [](size_t bas, size_t exp) { long long pow = 1LL;  while (exp-- > 0) pow *= bas; return pow; }(alf_len, n); // это просто вычисление alf_len в степени n ))
    vector<size_t> indexes(n);
    for (long long i = 0; i < total; ++i) {
        next_comb(i, alf_len, indexes);
        for (size_t j = 0; j < n; ++j) {
            cout << alf[indexes[j]];
        }
        cout << endl;
    }
}

int main() {
    gen2(abc, N);
}

Прикрутить 4 — не проблема. Можно параллелить аналогично http://rextester.com/HPLG75261.

как-то обошёлся гораздо меньшей кровью.

За счет рекурсии, от которой я как раз отказался.

Вроде даже попроще получилось.

В результате получили проблему — отвалился пункт 2.
Мы не можем теперь работать,
если количество комбинаций превышает максимум в long long. :)
Я в первом сообщении изначально писал,
что хотелось бы без длинной арифметики обойтись,
но потом убрал и как результат — Вы нарвались на те же грабли что и я. )))

Если это убрать, то уже многопоточность прикрутить хз как даже. )))
Хотя у меня есть одна идейка, но пока еще покурю на досуге эту тему. :)

А у тебя, видимо, припасено решение в темплейтно-функциональном (привет, STL!) стиле под флагом C++17? Выкладывай. Интересно посмотреть.

Нету ничего такого. )))

это просто вычисление alf_len в степени n ))

Ы-ы, жутковато, да. :D
А зачем лямбдой-то? )))

За счет рекурсии, от которой я как раз отказался.
В результате получили проблему — отвалился пункт 2.

С чего бы? У меня глубина рекурсии определяется количеством слов в «предложении», т.е. N. Длина слов вообще не при делах, размер алфавита обрабатывается в цикле. Параметры вызова функции gen не «распухают» — единственно, что увеличивается, это содержимое строки s, но оно в куче. Размер стека по умолчанию в MSVC++, если не ошибаюсь, 1Мб. Так что N может быть достаточно большим. Понятно, что можно задать такое N, что стека не хватит, но эту ситуацию можно отловить не доводя дела до runtime error. Если уж углубляться, то и памяти в куче может не хватить.

Мы не можем теперь работать, если количество комбинаций превышает максимум в long long. :)

Ну тогда остаётся только способ, предложенный в твоих ссылках, когда отлавливается «переполнение» при работе с массивом индексов. Кстати, в коде с многопоточной обработкой тоже высчитывается общее количество комбинаций. И не совсем корректно: во-первых, присваивание идёт переменной типа size_t aka unsigned int, который может быть меньше unsigned long long (я, кстати в своём коде упустил, что тип long long можно сделать беззнаковым); а во-вторых, неявное преобразование double, полученное от pow, к size_t с потенциальной потерей значимости. Так что твой пример многопоточного кода по вышепроцитированному критерию тоже можно отправить в корзину.

это просто вычисление alf_len в степени n ))

Ы-ы, жутковато, да. :D
А зачем лямбдой-то? )))

Ну вые@нулся ;) Не хотел вводить ещё одну функцию и не хотел писать код вычисления степени непосредственно в функции, чтобы типа «не засорять код». В итоге получилась та же фигня, только в профиль, да ещё и с обязательной поддержкой C++11. Но переписывать уже было лениво.

Как резюме: (1) исходная задача поставлена немного расплывчато. Хотелки и ограничения надо было указать более точно. (Впрочем, сам тоже грешу на эту тему.) (2) задача не для начинающих.

И не совсем корректно: во-первых, присваивание идёт переменной типа size_t aka unsigned int,

size_t — тип, который может выразить максимальный размер объекта на указанной платформе.
И он не обязан быть unsigned int,
ну и о x32 платформе я уже потихоньку забываю,
ибо времена её проходят на десктопах.

а во-вторых, неявное преобразование double, полученное от pow, к size_t с потенциальной потерей значимости.

В начальном коде был не std::pow. :)

Но переписывать уже было лениво.

Это всегда мешает, да? )))
А с другой стороны помогает
от всяких оверинженирингов. )))

Мы не можем теперь работать, если количество комбинаций превышает максимум в long long. :)
Я в первом сообщении изначально писал, что хотелось бы без длинной арифметики обойтись, но потом убрал и как результат — Вы нарвались на те же грабли что и я. )))

Если это убрать, то уже многопоточность прикрутить хз как даже. )))

Есть мысль как прикрутить многопоточность.

Использовать твою функцию генерации следующей последовательности. В массиве индексов каждый индекс изменяется от 0 до длины_алфавита - 1. Первый индекс изменяется медленнее всего. Для каждого потока задаём диапазон обработки по первому индексу из массива индексов длина_алфавита / общее_количество_потоков. Эту идею можно распространить и на следующие индексы для более равномерного разделения общего объёма вычислений по потокам, но код будет сложнее.

Или можно задавать на обработку потоку только очередной кусок с фиксированным первым индексом, или с фиксированными несколькими первыми индексами в массиве индексов.

А вот интересно, почему при многопоточной обработке при выводе результатов в поток не происходит «вклинивания» результатов из одного потока в результаты другого? Оператор << захватывает поток в монопольное пользование?

Оператор << захватывает поток в монопольное пользование?

Да, оно потокобезопасно, если выставлен sync_with_stdio.
Но опять же, безопасен лишь один вывод, т.е.

std::cout << str << "\n";

уже не будет безопасно.

Есть мысль как прикрутить многопоточность.

Есть идея, сделать шаг не в единичку, а в количество потоков.
Тогда первый поток запускаем с начальной комбинацией 1,
второй — с комбинацией 2, и т.д.
Каждый поток будет шагать по «своим комбинациям».

И ещё одно наблюдение. Твой многопоточный код из-за операции вывода на консоль при 8-ми потоках грузит проц на 15-20% (в пиках до 32%). А вот если вывод на консоль убрать — тогда честные 100% загрузки проца.

Твой многопоточный код из-за операции вывода на консоль при 8-ми потоках грузит проц на 15-20% (в пиках до 32%).

Ну так вывод же синхронизируется, так что,
по факту, другие потоки спят в это время,
поэтому и нагрузка такая — работает один поток,
остальные ждут или дорабатывают до момента синхронизации.