我試圖找出一種演算法，以k從 size 陣列中獲得所有可能的大小組合和排列n。
讓我們舉個例子：
輸入：
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 演算法，但它給出了陣列大小的所有可能排列：
如果我們回到我們的示例，QuickPerm 演算法會給出以下輸出：
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1 ,2], [3, 2, 1]].
uj5u.com熱心網友回復：
您的任務（所有組合的所有排列）可以使用常規遞回函式（如下所示）輕松解決，無需任何花哨的演算法。
在線嘗試！
#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, ],
uj5u.com熱心網友回復：
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
uj5u.com熱心網友回復：
您可以創建給定陣列的所有子集，然后對所有子集應用 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]
您可以使用這些向量的長度來計算結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452495.html