数组元素的所有置换一次在C ++中占用一定数量的元素 [英] All Permutation of an array elements taken certain number of element at a time in C++
本文介绍了数组元素的所有置换一次在C ++中占用一定数量的元素的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试一次获取一定数量元素的任何数组的所有置换集,例如,如果array = {1,2,3,4}
和r=3
,则可能的置换为24
.这是我使用递归的实现,但这没有得到预期的结果.
I am trying to get all set of permutation of any array taken certain number of element at a time for example if array = {1,2,3,4}
and r=3
then possible permutation will be 24
. Here is my implementation using recursion but this is not giving expected result.
void permutationUtil(vector<int> arr, vector<int> data, int start, int end, int index, int r) {
// Current permutation is ready to be printed, print it
if (index == r){
for (int j=0; j<r; j++)
printf("%d ", data[j]);
printf("\n");
return;
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a permutation with remaining elements
// at remaining positions
for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
data[index] = arr[i];
permutationUtil(arr, data, i + 1, end, index + 1, r);
}
}
void printPermutation(vector<int> arr, int n, int r) {
// A temporary array to store all permutation one by one
vector<int> data(n);
// Print all permutation using temprary array 'data[]'
permutationUtil(arr, data, 0, n - 1, 0, r);
}
推荐答案
您可以使用std::next_permutation
进行2次循环:
You may do it with 2 loop with std::next_permutation
:
void permutationUtilInner(std::vector<int> v,
std::function<void (const std::vector<int>&)> f)
{
do {
f(v);
} while (std::next_permutation(v.begin(), v.end()));
}
void permutationUtil(std::vector<int> v,
std::size_t r,
std::function<void (const std::vector<int>&)> f)
{
// remainder: range should be sorted for std::next_permutation
std::vector<bool> b(v.size() - r, false);
b.resize(v.size(), true);
std::sort(v.begin(), v.end());
do {
std::vector<int> sub;
for (std::size_t i = 0; i != b.size(); ++i) {
if (b[i]) {
sub.push_back(v[i]);
}
}
permutationUtilInner(sub, f);
} while (std::next_permutation(b.begin(), b.end()));
}
这篇关于数组元素的所有置换一次在C ++中占用一定数量的元素的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文