如何生成数组中所有长度为M的排列
如何生成数组中所有长度为M的排列
提问于 2017-01-27 03:41:57
假设我们有长度为N的数组，我需要在数组中生成长度为M的所有排列
我尝试使用next排列，但是如果我想生成长度为3的长度为5的数组的所有排列，我只得到前3个数字的排列。
下面是我的代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[5] = {1,2,3,4,5};
int m=3;
do {
for(int i=0;i<m;i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
} while(next_permutation(arr, arr+m));
return 0;
}提前谢谢。
回答 4
Stack Overflow用户
发布于 2017-01-27 08:06:31
有更快的解决方案(参见Knuth 4A)，但这个解决方案很简单，并且在最优的线性因子内。与您编写的内容相比，唯一的变化是(1) reverse语句(2) next_permutation的参数(n而不是m)。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[5] = {1, 2, 3, 4, 5};
int m = 3;
do {
for (int i = 0; i < m; i++) {
cout << arr[i] << " ";
}
cout << endl;
reverse(arr + m, arr + 5);
} while (next_permutation(arr, arr + 5));
return 0;
}Stack Overflow用户
发布于 2017-01-27 05:27:52
这将给出所有的顺序排列：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int arr[5] = {1,2,3,4,5};
int m=3;
int ct = 0;
do {
do {
for(int i=ct;i<ct+m;i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
} while(next_permutation(arr+ct, arr+ct+m));
ct++;
} while (ct + m <= 5);
return 0;
}对于所有的排列，尝试使用位操作。
Stack Overflow用户
发布于 2017-01-27 06:17:42
对于这种稍微定制的问题，最好的方法是回到老式的递归，并实现递归函数来给出输出。
这是一个示例解决方案。
#include <iostream>
using namespace std;
int n=5;
int arr[5] = {1,2,3,4,5};
int vis[5]; //same size as arr[]
int m=3;
int ans[3];
void gen(int total_taken) {
if(total_taken == m) {
//found one permutation
for(int i=0;i<m;i++) cout<<ans[i];
cout<<endl;
return;
}
for(int i=0;i<n;i++) {
if(vis[i]==0) {
vis[i]=1;
ans[total_taken] = arr[i];
gen(total_taken+1);
vis[i]=0;
}
}
}
int main()
{
//init n,m,ans[],arr[],vis[]
gen(0);
return 0;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41881631
复制相关文章
相似问题
腾讯云开发者
