大小 n 算法的所有可能组合和排列

Question

我正在尝试找出一种算法，从大小为 n 的数组中获得大小为 k 的所有可能组合和排列。

举个例子：

输入：

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

输出应该是：

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]]

我从查看 QuickPerm Algorithm 开始，但它给出了数组大小的所有可能排列：

如果我们回到我们的例子，QuickPerm 算法给出这个输出：

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

Answer 1

您可以创建给定数组的所有子集，然后对所有子集应用 quickPerm 算法。

[1,2,3] 的子集将是

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

现在，如果您对所有这些子集应用 quickPerm，您将获得：

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

您可以使用这些向量的长度来合并结果。

Answer 2

您的任务（所有组合的所有排列）可以使用常规递归函数轻松解决（正如我在下面所做的那样），无需任何花哨的算法。

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 << "], ";
    });
}

输出：

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

Answer 3

class CombinationsPermutation {
public:
    explicit CombinationsPermutation(size_t n, size_t k)
        : n { n }
    {
        indexes.resize(k);
        reset();
    }

    void reset()
    {
        std::iota(indexes.begin(), indexes.end(), 0);
    }

    const std::vector<size_t>& get() const
    {
        return indexes;
    }

    bool next()
    {
        if (std::next_permutation(indexes.begin(), indexes.end())) {
            return true;
        }
        auto it = indexes.rbegin();
        auto max_index = n - 1;
        while (it != indexes.rend() && *it == max_index) {
            --max_index;
            ++it;
        }
        if (it != indexes.rend()) {
            std::iota(it.base() - 1, indexes.end(), *it + 1);
            return true;
        }
        reset();
        return false;
    }

private:
    size_t n;
    std::vector<size_t> indexes;
};

https://godbolt.org/z/dex634fY1

大小 n 算法的所有可能组合和排列

All possible combinations and permutations of size n algorithm

c++

algorithm

combinations

permutation