#include <array>
#include <cstddef>
#include <vector>
#include <iostream>
template<typename T, int K, int N>
void generate_all_multisets(
std::array<T, K> const& alphabet,
std::vector< std::vector<T> >& all_words,
std::vector<T>& current_word,
int current_letter
)
{
if (current_letter == N) {
all_words.push_back(current_word);
for (auto k = 0; k != N; ++k)
std::cout << current_word[k];
std::cout << "\n";
return;
}
auto const tmp = current_word[current_letter];
for (auto letter = alphabet.begin(); letter != alphabet.end(); ++letter) {
current_word[current_letter] = *letter;
generate_all_multisets<T, K, N>(alphabet, all_words, current_word, current_letter + 1);
}
current_word[current_letter] = tmp;
}
template<typename T, int K, int N>
void generate_all_words(
std::array<T, K> const& alphabet,
std::vector< std::vector<T> >& all_words
)
{
// first word
std::vector<T> word(N, alphabet.front());
generate_all_multisets<T, K, N>(alphabet, all_words, word, 0);
}
int main()
{
std::array<int, 4> alphabet = { 1, 2, 3, 4};
auto const word_length = 3;
std::vector< std::vector<int> > all_words;
generate_all_words<int, 4, 3>(alphabet, all_words);
}
I2luY2x1ZGUgPGFycmF5PgojaW5jbHVkZSA8Y3N0ZGRlZj4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgaW50IEssIGludCBOPgp2b2lkIGdlbmVyYXRlX2FsbF9tdWx0aXNldHMoCiAgICBzdGQ6OmFycmF5PFQsIEs+IGNvbnN0JiBhbHBoYWJldCwgCiAgICBzdGQ6OnZlY3Rvcjwgc3RkOjp2ZWN0b3I8VD4gPiYgYWxsX3dvcmRzLCAKICAgIHN0ZDo6dmVjdG9yPFQ+JiBjdXJyZW50X3dvcmQsIAogICAgaW50IGN1cnJlbnRfbGV0dGVyCikKewogICAgaWYgKGN1cnJlbnRfbGV0dGVyID09IE4pIHsKICAgICAgICBhbGxfd29yZHMucHVzaF9iYWNrKGN1cnJlbnRfd29yZCk7CiAgICAgICAgZm9yIChhdXRvIGsgPSAwOyBrICE9IE47ICsraykgCiAgICAgICAgICAgIHN0ZDo6Y291dCA8PCBjdXJyZW50X3dvcmRba107CiAgICAgICAgc3RkOjpjb3V0IDw8ICJcbiI7CiAgICAgICAgcmV0dXJuOwogICAgfSAgIAoKICAgIGF1dG8gY29uc3QgdG1wID0gY3VycmVudF93b3JkW2N1cnJlbnRfbGV0dGVyXTsKICAgIGZvciAoYXV0byBsZXR0ZXIgPSBhbHBoYWJldC5iZWdpbigpOyBsZXR0ZXIgIT0gYWxwaGFiZXQuZW5kKCk7ICsrbGV0dGVyKSB7CiAgICAgICAgY3VycmVudF93b3JkW2N1cnJlbnRfbGV0dGVyXSA9ICpsZXR0ZXI7CiAgICAgICAgZ2VuZXJhdGVfYWxsX211bHRpc2V0czxULCBLLCBOPihhbHBoYWJldCwgYWxsX3dvcmRzLCBjdXJyZW50X3dvcmQsIGN1cnJlbnRfbGV0dGVyICsgMSk7CiAgICB9CiAgICBjdXJyZW50X3dvcmRbY3VycmVudF9sZXR0ZXJdID0gdG1wOyAKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVCwgaW50IEssIGludCBOPgp2b2lkIGdlbmVyYXRlX2FsbF93b3JkcygKICAgIHN0ZDo6YXJyYXk8VCwgSz4gY29uc3QmIGFscGhhYmV0LCAKICAgIHN0ZDo6dmVjdG9yPCBzdGQ6OnZlY3RvcjxUPiA+JiBhbGxfd29yZHMKKQp7CiAgICAvLyBmaXJzdCB3b3JkCiAgICBzdGQ6OnZlY3RvcjxUPiB3b3JkKE4sIGFscGhhYmV0LmZyb250KCkpOwogICAgZ2VuZXJhdGVfYWxsX211bHRpc2V0czxULCBLLCBOPihhbHBoYWJldCwgYWxsX3dvcmRzLCB3b3JkLCAwKTsKfQoKaW50IG1haW4oKQp7CiAgICBzdGQ6OmFycmF5PGludCwgND4gYWxwaGFiZXQgPSB7IDEsIDIsIDMsIDR9OwogICAgYXV0byBjb25zdCB3b3JkX2xlbmd0aCA9IDM7IAoKICAgIHN0ZDo6dmVjdG9yPCBzdGQ6OnZlY3RvcjxpbnQ+ID4gYWxsX3dvcmRzOwogICAgZ2VuZXJhdGVfYWxsX3dvcmRzPGludCwgNCwgMz4oYWxwaGFiZXQsIGFsbF93b3Jkcyk7Cn0=