毕设终于进入尾声,在毕设的代码中有一部分要对整数求全排列。如0 1 3的全排列是013 031 103 130 301 310。本来觉得写个全排列还有点复杂,不想去弄,直接switch case,因为最多就3个元素。
最后希望扩大测试范围,全排列的元素数量上升到了4,再switch case,就比较慢了,并且也太没技术含量了。所以简单的写了一个全排列的算法。
std::vector<int> quanpailie(std::vector<int>& v)
{
std::vector<int> result; if(v.empty()) return result;
if(v.size()==1)
{
result.push_back(v[0]);
result.push_back(-1);
return result;
}
for(int i=0;i<v.size();++i)
{
int head=v[i];
std::vector<int> t(v);
t.erase(t.begin()+i);
t=quanpailie(t);
result.push_back(head);
for(int j=0;j<t.size()-1;++j)
{
if(j>=1 &&t[j-1]==-1)
{
result.push_back(head);
}
result.push_back(t[j]);
}
result.push_back(-1);
}
return result;
}
int main(int argc, char *argv[]) {
int a[]={1,2,3,4};
std::vector<int> t;
for(int i=0;i<4;++i) t.push_back(a[i]);
t=quanpailie(t);
return 1;
}
算法是递归的,应该说效率还可以不算太高,最好把vector改成list。
另外算法也是适用于任意对象的,只需要把int改成其他对象即可。当然也要换一个其他对象的分隔符。本例中分隔符是-1
也就是得到的全排列是1 2 3 -1 1 3 2 -1 3 1 2 -1等等
原文链接: https://www.cnblogs.com/zhangzheng/archive/2013/03/09/2950396.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/80093
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!