Рекурсивные вложенные циклы for для реализации определенных перестановок во время выполнения

Question

Я пытаюсь написать рекурсивную функцию, которая реализует n вложенных циклов for, где n определяется во время выполнения, что дает мне все возможные комбинации чисел 1-x. Таким образом, для х = 3 это будет

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

Я хочу, чтобы каждая перестановка сохранялась в векторе. Я нашел много ответов о том, как реализовать вложенные циклы for как рекурсивные функции, но ни один из них не дал желаемого результата. Затем некоторые ответы, которые работают только с жестко запрограммированным количеством циклов for, которые я просто не могу заставить работать динамически (число определяется во время выполнения). Затем некоторые ответы, где одна перестановка имеет только одно из каждого числа, что мне не нужно (мне также нужны перестановки, такие как 2-2-2 или 3-3-3). Это кажется такой простой проблемой, но я просто не могу понять это. Любая помощь будет безумно признательна

Answer 1

Я думаю, что это должно сработать:

#include <iostream>
#include <vector>

void getPerm(int from, int to, std::vector<int>& curr, std::vector<std::vector<int>>& result) {
    bool alreadySetToOne  = false;
    int  nextFrom = 0;
    if (curr.size() == to) {
        result.push_back(curr);
        return;
    }

    if (from > 1 && !alreadySetToOne) {
        from = 1;
        alreadySetToOne = true;
    }

    for (int i=from; i <= to; ++i) {
        curr.push_back(i);
        getPerm(i, to, curr, result);
        curr.pop_back();
    }
}

int main() {
    auto n = 0;
    std::vector<std::vector<int>> results;
    std::vector<int> curr;
    std::cout << "Put number ...\n";
    std::cin >> n;
    getPerm(1, n, curr, results);


    //Check results
    for (int i=0; i < results.size(); ++i) {
        for (int j = 0; j < results[i].size(); ++j) {
            std::cout << results[i][j] << ", ";
        }
        std::cout << std::endl;
    }
}

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

Answer 2

void Foo(vector<vector<int>>& list, const int& n)
{
    if(list.empty())
    {
        list.push_back(vector<int>(n,1));
        return Foo(list,n);
    }

    vector<int> entry(list.back());
    for(int i=n-1; i>=0; i--)
    {
        if(entry.at(i) < n)
        {
            entry[i]++;
            list.push_back(entry);

            return Foo(list,n);
        }

        entry[i] = 1;
    }
}

// test case
vector<vector<int>> list;
Foo(list,3);

Если пусто, это будет инициализировать вектор размером n для целых чисел равным 1. Затем на каждой итерации будет клонироваться последняя запись и циклически понижаться индексы от наименьшего до наиболее значимого, увеличиваться, если оно меньше, чем n, и повторяться или же сбрасываться до 1 и продолжаем до следующего наиболее значимого индекса, пока он не будет завершен.