All possible combinations and permutations of size n algorithm

Question

I'm trying to figure out an algorithm to have all possible combinations and permutations of size k from an array of size n.

Let's have an example:

Input:

n = 3 => [1, 2, 3]

Output should be:

k = 1 => [[1], [2], [3]]
k = 2 => [[1, 2], [1, 3], [2, 3], [2, 1], [3, 1], [3, 2]]
k = 3 => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1 ,2], [3, 2, 1]]

I started by looking at the QuickPerm Algorithm but it gives all possible permutations for the size of the array:

If we go back to our example, the QuickPerm algorithm gives this output:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1 ,2], [3, 2, 1]].

Answer 1

Your task (all permutations of all combinations) can be easily solved using regular recursive function (as I did below) without any fancy algorithm.

Try it online!

#include <vector>
#include <functional>
#include <iostream>

void GenCombPerm(size_t n, size_t k, auto const & outf) {
    std::vector<bool> used(n);
    std::vector<size_t> path;
    std::function<void()> Rec =
        [&]{
            if (path.size() >= k) {
                outf(path);
                return;
            }
            for (size_t i = 0; i < used.size(); ++i) {
                if (used[i])
                    continue;
                used[i] = true;
                path.push_back(i);
                Rec();
                path.pop_back();
                used[i] = false;
            }
        };
    Rec();
}

int main() {
    std::vector<size_t> a = {1, 2, 3};
    GenCombPerm(a.size(), 2, [&](auto const & v){
        std::cout << "[";
        for (auto i: v)
            std::cout << a[i] << ", ";
        std::cout << "], ";
    });
}

Output:

[1, 2, ], [1, 3, ], [2, 1, ], [2, 3, ], [3, 1, ], [3, 2, ],