permutation(242)

发表于   |   分类于

排列算法stl里面的next_permutation和prev_permutation

next_permutation

  1. 从尾部开始往前寻找两个相邻的元素,第1个元素i，第2个元素j（从前往后数的），且i<j
  2. 在[j,end)中寻找一个最小的k使其满足A[i]<A[k],将i与k交换
  3. [j,last)范围的元素置逆（颠倒排列）

1,3,2-> 2,1,3过程
i是1，j是3. k是3；互换后是3,1,2; 由于j是3，逆序就是2,1,3了

prev_permutation

  1. 从尾部开始往前寻找两个相邻的元素,第1个元素i，第2个元素j（从前往后数的），且i>j
  2. 从最尾端开始往前寻找第一个小于i的元素，令它为k, 讲i和k对调
  3. j之后颠倒
// //