首页
登录 | 注册

字典序法求解全排列问题

对给定的字符集中的字符规定了一个先后关系,在此基础上规定两个全排列的先后是从左到右逐个比较对应的

字符的先后。

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:
123,132,213,231,312,321。
※※ 一个全排列可看做一个字符串,字符串可有前缀、后缀。

生成给定全排列的下一个排列:
所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。

[例]  839647521是1--9的排列。1—9的排列最前面的是123456789,最后面的是987654321,从右向左扫描若都是增的,就到了987654321,也就没有下一个了。否则找出第一次出现下降的位置。

一般而言,设P是[1,n]的一个全排列

找出最远的一对(Pi

 

关于组合数组的字典序生成法是这样进行的:(最简洁)

  对于给定的一个数,首先从右边找到第一个相邻"逆序对",现假设下一个要找的数比这个数大,且中间没有一个数比前者大、比后者小。那么这个"逆序对"的定义是就是满足
num[ i ]< num[ i+ 1 ](假设这个整数是以数组的形式存储的),然后再重新从右边起找出第一个比那个"逆序对"的较小者 要大的数,交换他们,再将那个较小数下标后面的子数组反转。。。。。

STL有个这样的函数:

  1. 这是一道典型的全排列问题。可以用STL的next_permutation()函数,标准库全排列next_permutation()

  2. 返回值:bool类型

  3. 分析next_permutation函数执行过程:
  4. 假设数列 d1,d2,d3,d4……范围由[first,last)标记,调用next_permutation使数列逐次增大,这个递增过

  5. 程按照字典序。

  6. #include <iostream>
  7. #include <algorithm>
  8. using namespace std;

  9. int main()
  10. {
  11.     int a[] = {1,2,3};
  12.     do
  13.     {
  14.         cout << a[0] << " " << a[1] << " " << a[2] << endl;
  15.     }
  16.     while (next_permutation(a,a+3));//while放在前面的话 要考虑如何输出第一个 1 2 3,因为

  17. 数组一直在递增
  18.     return 0;
  19. }
  20. /*
  21. 1 2 3
  22. 1 3 2
  23. 2 1 3
  24. 2 3 1
  25. 3 1 2
  26. 3 2 1
  27. Press any key to continue*/


 

 

 


相关文章

  • 033期:跑狗玄机一字记之曰:<路> 運去雷轟,時來風送.狹路相逢路不通! 闖南走北,往來西東.回頭已是白頭翁! 玄机测字:[流] 033期:黄大仙特 码诗------≤做事鲁莽,小题大做的动物≥-- 開:? 準! 解: 032 ...
  • 写了一个小程序分析<Python科学计算>第二版目前的状态.在下面的目录中,[ ]中的两个数字分别表示章节的文字数和示例代码行数.上级目录的的数字和下级目录中的合计.目前全书有32万字,9100行示例代码. import os ...
  •         本文介绍的SPL排序优化技巧,除了提供常规的排序算法外,还根据不同场景下的数据特性提供了排序的替代算法,从而减少比较次数和IO量,提升运算性能. 1内存排序         当数据可以轻松装入内存时,可以使用SPL的内存排序 ...
  • 大数据学习~Hadoop初识三Yarn模式
    2.0以前的Hadoop 在JobTracker 过多的TaskScheduler 集中过来,容易造成内存,cpu不够用的情况.增加了任务执行失败的风险. 在2.0的YARN 新的YARN模式如下 从图中我们可以看到 原先的JobTrack ...
  • TIFF图像文件格式介绍
    1 什么是TIFF? TIFF是Tagged Image File Format的缩写.在现在的标准中,只有TIFF存在, 其他的提法已经舍弃不用了.做为一种标记语言,TIFF与其他文件格式最大的不同在于除了图像数据,它还可以记录很多图像的 ...
  • 将传统的 2D 视频转为 3D (伪 3D ,左右眼)视频-T
    将传统的 2D 视频转为 3D (伪 3D ,左右眼)视频 当带上 VR 头戴设备时,观看普通的 2D 视频时,是无法正常观看的,需要将 2D 转为左右眼的视频,下面介绍一下将 2D 视频转换为左右眼的视频. 首先介绍一下原理,为了达到左右 ...

2020 unjeep.com webmaster#unjeep.com
12 q. 0.012 s.
京ICP备10005923号