C++ vector 容器的全排列算法 next_permutation

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: C++ vector 容器的全排列算法 next_permutation

问题源于我要对4个数进行排列,自己用了笨拙的穷举算法一个4重循环也得到结果,其中对有相同字母的做排序加删除相邻相等元素的处理。可是如果对100个数进行排列难道用100重循环,后来发现C++11有现成的permute算法,只要一个排序sort()加一个do-while循环就能轻松实现。permute算法有两个next_permutation (vector.begin(), vector.end()); prev_permutation (vector.begin(), vector.end()); 具体的用法以及区别,见下列源代码:



穷举算法代码:

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
void initVect(vector<string>&);
void changeVect(string&);
void permuteVect(vector<string>&,vector<string>&);
int main(void)
{
  vector<string> t4,t3;
  permuteVect(t4,t3);
  cout<<"四个不同字母的排列:"<<endl;
  for (auto v:t4) cout<<v<<" "; cout<<endl<<endl;
  cout<<"四个字母其中2个相同的排列:"<<endl;
  for (auto v:t3) cout<<v<<" "; cout<<endl;
  return 0;
}
void initVect(vector<string> &s)
{
  string n[4]={"A","B","C","D"};
  s.clear();
  for (int a=0;a<4;a++)
    for (int b=0;b<4;b++)
      for (int c=0;c<4;c++)
        for (int d=0;d<4;d++)
          if (a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d)
            s.push_back(n[a]+n[b]+n[c]+n[d]);
}
void changeVect(string &s) 
{
  for (int i=0;i<4;i++)
    if (s[i]=='D') s[i]='A';
}
void permuteVect(vector<string>&t4,vector<string>&t3)
{
  initVect(t4);
  t3=t4;
  for_each(t3.begin(),t3.end(),changeVect);
  sort(t3.begin(),t3.end());
  for (auto it=t3.begin();it!=t3.end();it++)
    if (*it==*(it+1)) t3.erase(it--); 
}
/*
执行结果:
四个不同字母的排列:
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA
CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
四个字母其中2个相同的排列:
AABC AACB ABAC ABCA ACAB ACBA BAAC BACA BCAA CAAB CABA CBAA
--------------------------------
Process exited after 1.003 seconds with return value 0
请按任意键继续. . .
*/


permutation算法代码:

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
    vector<string> n1={"C","D","A","B"}; //不按顺序可以测试sort()的必要性 
    vector<string> n2={"A","A","B","C"};
    vector<string> t4,t3;
  sort(n1.begin(),n1.end()); //next_permutation要升序排列,否则会漏算 
    do t4.push_back(n1[0]+n1[1]+n1[2]+n1[3]);
    while(next_permutation(n1.begin(),n1.end()));
  sort(n2.begin(),n2.end());
  reverse(n2.begin(),n2.end()); //prev_permutation要降序排列
    do t3.push_back(n2[0]+n2[1]+n2[2]+n2[3]);
    while(prev_permutation(n2.begin(),n2.end())); 
  cout<<"四个不同字母的排列:"<<endl;
  for (auto v:t4) cout<<v<<" "; cout<<endl;
  cout<<endl<<endl<<"四个字母其中2个相同的排列:"<<endl;
    for (auto v:t3) cout<<v<<" "; cout<<endl;
  return 0;
}
/*
四个不同字母的排列:
ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA
CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA
四个字母其中2个相同的排列:
CBAA CABA CAAB BCAA BACA BAAC ACBA ACAB ABCA ABAC AACB AABC
--------------------------------
Process exited after 0.9859 seconds with return value 0
请按任意键继续. . .
*/


注:对数组进行排列的写法: int Array[lenth]={...,...}; next_permutation(Array, Array+lenth);

 


算法的简单应用:

题目:数字0,1,2,3有多少种排列,可以组成多少个不同的四位数?

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
  int y=1,r=0123,h=0;
    vector<int> m,n={0,1,2,3};
    //已升序排序略;第1组排列0123不能组成四位数,略;也是设y=1,r=0123的用意
    for (y;next_permutation(n.begin(),n.end());y++){
      r=1000*n.at(0)+100*n.at(1)+10*n.at(2)+n.at(3);
      if (r>1000) m.push_back(r),h++;
  }
    cout<<"0,1,2,3共有"<<y<<"种排列,能组成"<<h<<"个不同的四位数,如下:"<<endl;
    for (auto n:m) cout<<n<<" ";
  return 0;
}
/*
运行结果:
0,1,2,3共有24种排列,能组成18个不同的四位数,排列如下:
1023 1032 1203 1230 1302 1320 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120
3201 3210
--------------------------------
Process exited after 0.9471 seconds with return value 0
请按任意键继续. . .
*/


温馨提示:

  next_permutation()用while-do或for循环会漏第1组排列,建议使用do-while循环

改进一下代码,增加一个临时容器来存放所有的排列,然后在临时容器中读取所有四位数:

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
int vect2number(vector<int> vect)
{
  int i=0,j=1000;
  for (auto v:vect) i+=v*j,j/=10;
  return i;
}
int main(void)
{
  int y=0,r=0;
    vector<int> m,n={3,2,1,0};
  sort(n.begin(),n.end());
    do m.push_back(vect2number(n));
    while(next_permutation(n.begin(),n.end()));
    for (auto n:m) {y++; if (n>1000) r++;} //注:此n非彼n,循环体变量与循环体外的变量无关
    cout<<"0,1,2,3共有"<<y<<"组排列,能组成"<<r<<"个不同的四位数,排列如下:"<<endl;
    for (auto n:m) if (n>1000) cout<<n<<" "; cout<<endl;
  return 0;
}
/*
注: do m.push_back(vect2number(n));
    while(next_permutation(n.begin(),n.end()));
可用以下2行代替: 
  m.push_back(vect2number(n));
    for (;next_permutation(n.begin(),n.end());) m.push_back(vect2number(n));
运行结果:
0,1,2,3共有24组排列,能组成18个不同的四位数,排列如下:
1023 1032 1203 1230 1302 1320 2013 2031 2103 2130 2301 2310 3012 3021 3102 3120
3201 3210
--------------------------------
Process exited after 0.4442 seconds with return value 0
请按任意键继续. . .
*/


附录:

next_permution基本算法思想


1.首先从最尾端开始往前寻找两个相邻元素,令第一元素为*i,第二元素为*ii,且满足*i<*ii。


2.找到这样一组相邻元素后,再从最尾端开始往前检验,找出第一个大于*i的元素,令为*j,将i,j元素对调(swap)。


3.再将ii之后的所有元素颠倒(reverse)排序。

举个实例,假设有序列{0,1,2,3,4},下图便是套用上述演算法则,一步一步获得“下一个”排列组合。图中只框出那符合“一元素为*i,第二元素为*ii,且满足*i<*ii ”的相邻两元素,至于寻找适当的j、对调、逆转等操作并未显示出。


20210124211411357.png


目录
相关文章
|
15天前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
42 4
|
1天前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
11 0
|
2月前
|
存储 C++ 索引
【C++打怪之路Lv9】-- vector
【C++打怪之路Lv9】-- vector
23 1
|
2月前
|
编译器 C++
【C++】—— vector模拟实现
【C++】—— vector模拟实现
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
33 0
|
2月前
|
算法 C++ 容器
C++之打造my vector篇(下)
C++之打造my vector篇(下)
30 0
|
2月前
|
存储 编译器 C++
C++之打造my vector篇(上)
C++之打造my vector篇(上)
29 0
|
2月前
|
算法 C++ 容器
【C++】—— vector使用
【C++】—— vector使用
|
2月前
|
存储 缓存 C++
C++番外篇——list与vector的比较
C++番外篇——list与vector的比较
23 0
|
2月前
|
C++
C++番外篇——vector的实现
C++番外篇——vector的实现
47 0