STL模板整理 全排列
概念:
从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。如果这组数有n个,那么全排列数为n!个。
比如a,b,c的全排列一共有3!= 6 种 分别是{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}。
使用方法
这里先说两个概念:“下一个排列组合”和“上一个排列组合”,对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
1)next_permutation:求下一个排列组合
a.函数模板:next_permutation(arr, arr+size);
b.参数说明:
arr: 数组名
size:数组元素个数
c.函数功能: 返回值为bool类型,当当前序列不存在下一个排列时,函数返回false,否则返回true,排列好的数在数组中存储
d.注意:在使用前需要对欲排列数组按升序排序,否则只能找出该序列之后的全排列数。
比如,如果数组num初始化为2,3,1,那么输出就变为了:{2 3 1} {3 1 2} {3 2 1}
2)prev_permutation:求上一个排列组合
a.函数模板:prev_permutation(arr, arr+size);
b.参数说明:
arr: 数组名
size:数组元素个数
c.函数功能: 返回值为bool类型,当当前序列不存在上一个排列时,函数返回false,否则返回true
d.注意:在使用前需要对欲排列数组按降序排序,否则只能找出该序列之后的全排列数。
代码:
#include <iostream> #include <algorithm> using namespace std; int main () { ,,}; cout<<"用prev_permutation对3 2 1的全排列"<<endl; do { cout << arr[] << ] << ]<<'\n'; } ) ); ///获取上一个较大字典序排列,如果3改为2,只对前两个数全排列 ,,}; cout<<"用next_permutation对1 2 3的全排列"<<endl; do { cout << arr1[] << ] << ] <<'\n'; } ) ); ///获取下一个较大字典序排列,如果3改为2,只对前两个数全排列 ; }
最新文章
- KindEditor编辑器For DotNet控件
- Matlab最短路径问题记录
- Balanced Teams (USACO Jan Bronze 2014)
- Ubuntu 14.10 下进程实时IO监控iotop命令详解
- 设置field的背景颜色以及对stylesheet的理解
- Crystal Report在.net中的两种显示方式
- MVC中前台如何向后台传递数据------$.get(),$post(),$ajax(),$.getJSON()总结
- Objec类和final关键字的用法
- windows internal读书笔记
- mabatis mapper开发规范
- 两个HTML,CSS布局实例
- PHP实现简单的评论与回复功能还有删除信息
- CSS核心内容之盒子模型
- JEECG中出现Java.sql.SQLException: Value &#39;xxxx&#39; can not be represented as java.sql.Timestamp的解决办法
- Python学习---字符串处理
- redis---安装和开启和关闭
- 筛选法求n以内所有的素数
- python 正则表达提取方法 (提取不来的信息print不出来 加个输出type 再print信息即可)
- DAU预测
- window.load 和$(document).ready() 、window.load和body onload区别
热门文章
- c# 计算时间差---天数
- 51Nod 1049最大子段和 | 模板
- HDU 5901 Count primes 大素数计数
- 【转】js JavaScript 的性能优化:加载和执行
- UIPikerView的属性---iOS-Apple苹果官方文档翻译
- POj 2104 K-th Number (分桶法+线段树)
- 在使用ubuntu16.04+python3.5 下使用pip3出现pip3 error - &#39;_NamespacePath&#39; object has no attribute &#39;sort&#39;
- eureka服务端
- url编码模块
- aptitude约等于apt-get的工具