解题思路:栈具有先进后出、后进先出的特点,因此,任何一个调度结果应该是1 ,2 ,3 ,4全排列中的一个元素。由于进栈的顺序是由小到大的,所以出栈序列应该满足以下条件:对于序列中的任何一个数其后面所有比它小的数应该是倒序的。据此,本题可以通过算法产生n 个数的全排列,然后将满足出栈规则的序列输出。
那么第一个问题就是对火车出战可能顺序的全排列:
对于一个系列的全排列有一下几种方法:
number 1:
借助于STL库中的next_permutation函数。next_permutation的作用就是计算全排列。
next_permutation(str,str+strlen(str))是一个求str数组元素的下一个排列的函数。如果要走遍所有的排列数组元素必须已经有小到大有序!还有一个prev_permutation,要求由大到小有序。
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int array[] = {1, 2, 3, 4};
- const int iArraySize = sizeof(array)/sizeof(int);
- int main()
- {
- int iCnt = 0;
- cout << iArraySize << endl;
- sort(array, array + iArraySize); //这里就是要求数组元素有小到大有序
- do
- {
- for(int i = 0; i < iArraySize; i++)
- {
- cout << array[i];
- }
- cout << " ";
- iCnt++;
- } while (next_permutation(array, array + iArraySize));
- cout << endl;
- cout << "Total number: " << iCnt << endl;
- return 0;
- }
number2:
不用STL函数,利用递归思想进行排列
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- int array[] = {1, 2, 3, 4};
- const int iArraySize = sizeof(array)/sizeof(int);
- //删除str的第n个字符
- void DeleteCharAt(string& str, int n)
- {
- if (n < 0 || n >= str.length())
- {
- return;
- }
- string tmpStr(str.substr(n + 1));
- str = str.substr(0, n) + tmpStr;
- }
- //base 以该字符串作为基础字符串,进行选择性组合。
- //buff 所求字符串的临时结果
- //result 存放所求结果
- void ListAll(string& strBase, string strBuff, vector<string>& result)
- {
- if (strBase.length() <= 0)
- {
- result.push_back(strBuff);
- }
- for(int i = 0; i < strBase.length(); i++)
- {
- string tmp(strBase);
- DeleteCharAt(tmp, i);
- ListAll(tmp, strBuff + strBase[i], result);
- }
- }
- int main(){
- int iCnt = 0;
- string str = "1324";
- vector<string> vResult;
- ListAll(str, "", vResult);
- //Output the result
- for (int i = 0; i < vResult.size(); ++i)
- {
- cout << vResult[i] << " ";
- }
- cout << "/n";
- cout << "Total number: " << vResult.size() << endl;
- return 0;
- }
- int i,j,k,l,m,flag=1,b[2];
- for(i=0;i<n;i++) /* 对每个str[i] 判断其后比它小的数是否为降序序列*/
- {
- m=0;
- for(j=i+1;j<n&&flag;j++)
- {
- if (str[i]>str[j])
- {
- if (m==0) b[m++]=str[j];//记录str[i]后比它小的数
- else
- {
- //如果之后出现的数比记录的数还大,改变标记变量
- if (str[j]>b[0]) flag=0;
- //否则记录这个更小的数
- else b[0]=str[j];
- }
- }
- }
- }
最后就可以输出满足条件的组合了。
非递归方法求全排列:
1、算法简述
要考虑全排列的非递归实现,先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。
如何计算字符串的下一个排列了?来考虑"926520"这个字符串,我们从后向前找第一双相邻的递增数字,"20"、"52"都是非递增的,"26 "即满足要求,称前一个数字2为替换数,替换数的下标称为替换点,再从后面找一个比替换数大的最小数(这个数必然存在),0、2都不行,5可以,将5和2交换得到"956220",然后再将替换点后的字符串"6220"颠倒即得到"950226"。
如果达到这个数的最大,比如1234-à4321,这个时候就结束整个循环。
如果输入是一个非最小数,如1324,则将它转换为最小数,如1234,再进行排序。排序算法用快排,可以自己写一个,如果快排不会的话,就先看会再来接着看,或者自己想一个靠谱的算法,也可以直接用VC库中的qsort(s , n , sizeof(s[0]) , cmp);各参数是什么意思就自己在下面多花点时间吧。
OK,下面看代码分析
2、代码分析
1 Prem( char *s ) //全排列函数 2 { 3 char *pEnd = s + strlen(s) - 1; 4 char *p = pEnd; //p代表替换点 5 //q代表替换点的下一个数 ,pMax 代表替换点后比替换点大的最小数 6 char *q = new char,*pMax = new char; //注意初始化!!! 7 while (p != s) //p == s 就结束循环 8 { 9 q = p;10 p--;11 if (*p < *q)12 {13 pMax = FindMaxForOne(p,pEnd); //找与替换点交换的点14 Swap(p,pMax); //交换15 Reverse(q,pEnd); //将替换点后所有数进行反转16 Print(s); //输出17 p = pEnd; //将替换点置最后一个点,开始下一轮循环18 }19 if (s == p) break; //结束条件20 }21 }