温州网站公司,室内设计师怎么找,网站程序和数据库,联通官网枚举所有排列的另一个方法是从字典序最小排列开始#xff0c;不停调用“求下一个排列”的过 程。 全排列的个数A(N,N)(N)(N-1)…*2*1N! 下一个排列#xff1a;通常按照升序顺序#xff08;字典序#xff09;获得下一个排列 stl
next_permutation找下一个排列的算法
如…枚举所有排列的另一个方法是从字典序最小排列开始不停调用“求下一个排列”的过 程。 全排列的个数A(N,N)(N)(N-1)…*2*1N! 下一个排列通常按照升序顺序字典序获得下一个排列 stl
next_permutation找下一个排列的算法
如果一个数组arr[]中存在重复元素next_permutation是否工作正常呢
STL使用“!(*i *j)”进行判断大小若相等则继续寻找这样就会跳过重复的元素进而跳过重复的全排列如1,2,2; 和1,2,2。
返回值
当返回为1时表示找到了下一全排列返回0时表示无下一全排列。注意如果从begin到end为降序则表明全排列结束。
原理
一个目的不断地找最接近这个排列的下个排列直到全部降序为止
templatecalss BidrectionalIterator
bool next_permutation(BidrectionalIterator first,BidrectionalIterator last)
{ if(first lase) return false; /* 空区间 */ BidrectionalIterator i first; i; if(i last) return false; /* 只有一个元素 */ i last; /* i指向尾端 */ --i; for(;;) { BidrectionalIterator ii i; --i; /* 以上锁定一组(两个)相邻元素 */ if(*i *ii) /* 如果前一个元素小于后一个元素 */ { BidrectionalIterator j last; /* 令j指向尾端 */ while(!(*i *--j)); /* 由尾端往前找直到遇到比*i大的元素 */ iter_swap(i,j); /* 交换i,j */ reverse(ii,last); /* 将ii之后的元素全部逆序重排 */ return true; } if(i first) /* 进行至最前面了 */ { reverse(first,last); /* 全部逆序重排 */ return false; } }
}
怎么用
#includecstdio
#includealgorithm //包含next_permutation
using namespace std;
int main( ) { int n, p[10]; scanf(%d, n); for(int i 0; i n; i) scanf(%d, p[i]); sort(p, pn); //排序得到p的最小排列 do { for(int i 0; i n; i){printf(%d , p[i]); //输出排列p}printf(\n); } while(next_permutation(p, pn)); //求下一个排列 return 0;
}
do…while 循环是 while 循环的变体。在检查while()条件是否为真之前该循环首先会执行一次do{}之内的语句然后在while()内检查条件是否为真如果条件为真的话就会重复do…while这个循环,直至while()为假。
