方法一：暴力搜索。
比较容易想到，先按照全排列的方法，找出火车进站序列的全排列。从全排列序列中找到符合出站规则的序列，再将所有的合法序列排序，最后依次打印输出。
出站规则：用栈储存入站火车序号，另一边用一个指针顺序遍历当前的全排列序列，对比当前栈顶序号是否与指针所指的全排列序列号相等。
相等就指针右移，栈顶序号出栈。若栈空就进栈下一个火车序号，继续与指针所指序号对比。
时间复杂度：O(n*n!)，空间复杂度O(catalan(n))，排序时用到了卡特兰数大小的空间。
/*从全排列序列中找出正确的出栈序列*/
#include <stdio.h>
int p=0;
void legal(int* a,int* b,int len,int c[][len],long d[][2]){//判断全排列的其中一个序列是否合法，并将值存入out
int in[len],top=0,i=1,j=0,flag=0;//top为入站序列的栈顶指针,i为入站序列指针，j为出站序列指针
in[top]=a[0];
while(j<len){//如果还有火车没有出站
if(in[top]==b[j]){
top--;
if(top==-1 && i<len){//车站空就入站
in[++top]=a[i++];
}
j++;
}
else if(i<len){
in[++top]=a[i++];
}
else{
flag=1;
break;
}
}
if(!flag){//合法就输出该序列
long sum=0;
for(int j=0;j<len;j++){
c[p][j]=b[j];
sum=10*sum+b[j];
}
d[p][0]=sum;
d[p][1]=p;
p++;
}
}
void sort(int* a,int* b,int start,int len,int c[][len],long d[][2]){//全排列出站序列，a[]为原入站序列，b[]为全排列序列
int t;
if(start>=len){
legal(a,b,len,c,d);
}
for(int i=start;i<len;i++){
if(start!=len){//交换两值后，对剩余len-i个元素全排列
t=b[start];
b[start]=b[i];
b[i]=t;
}
sort(a,b,start+1,len,c,d);
if(start!=len){//回溯，返回交换之前的状态
t=b[start];
b[start]=b[i];
b[i]=t;
}
}
}
int catalan(n){//计算卡特兰数
long x1=1,x2=1;
for(int i=n;i>1;i--){
x1*=i;
}
for(int i=2*n;i>n;i--){
x2*=i;
}
x2/=x1*(n+1);
return x2;
}
void bubble_sort(long a[][2],int n){
for(int i=0;i<n-1;i++){
long t1,t2,flag=0;
for(int j=n-1;j>i;j--){
if(a[j-1][0]>a[j][0]){
t1=a[j][0];t2=a[j][1];
a[j][0]=a[j-1][0];
a[j][1]=a[j-1][1];
a[j-1][0]=t1;
a[j-1][1]=t2;
flag=1;
}
}
if(!flag){
return;
}
}
}
int main(){
int N;scanf("%d",&N);
int a[11]={0},stack[N],in[N],I=0,t;
int NN=catalan(N);
int out[NN][N];long out1[NN][2];
while(scanf("%d",&t)!=EOF){
a[t]=1;
stack[I++]=t;//stack[]用于储存入站火车序号
}
t=0;
for(int i=1;i<11;i++){//为了优化最后排序的次数，in[]按序号大小存储入站火车号
if(a[i]){
in[t++]=i;
}
}
sort(stack,in,0,N,out,out1);
bubble_sort(out1,NN);
for(int i=0;i<NN;i++){
for(int j=0;j<N;j++){
printf("%d ",out[out1[i][1]][j]);
}
printf("\n");
}
}
执行耗时23ms，消耗内存560KB
优化：用按字典序的全排列，边排边输出，不用再排序。（c++可以用next_permutation()函数实现去重递增的字典排序）
时间复杂度：O(n*n!)，空间复杂度O(n)，最优的空间利用。
/*从全排列序列中找出正确的出栈序列*/
#include<stdio.h>
void legal(int* a,int* b,int len){//判断全排列的其中一个序列是否合法
int in[len],top=0,i=1,j=0,flag=0;//top为入站序列的栈顶指针,i为入站序列指针，j为出站序列指针
in[top]=a[0];
while(j<len){//如果还有火车没有出站
if(in[top]==b[j]){
top--;
if(top==-1 && i<len){//车站空就入站
in[++top]=a[i++];
}
j++;
}
else if(i<len){
in[++top]=a[i++];
}
else{
flag=1;
break;
}
}
if(!flag){//合法就输出该序列
for(int j=0;j<len;j++){
printf("%d ",b[j]);
}
printf("\n");
}
}
int search(int* a,int key,int low,int high){//二分查找
int mid;
while(low<=high){
mid=(low+high)/2;
if(a[mid]==key){
return mid;
}
else if(a[mid]<key){
high=mid-1;
}
else{
low=mid+1;
}
}
if(a[mid]>key){
return mid;
}
else{
return mid-1;
}
}
void swap(int* a,int* b){//交换
int c;
c=*a;*a=*b;*b=c;
}
void sort(int* a,int n,int* b){//改变当前序列为全排列按字典输出的下一个序列
legal(b,a,n);
int pos=n-1;
while(pos>0 && a[pos]<a[pos-1]){
pos--;
}
if(!pos){//已经完全逆序了就中止退出
return;
}
else{
int p=search(a,a[pos-1],pos,n-1);//二分查找确定交换位置
swap(&a[pos-1],&a[p]);
}
for(int i=pos;i<=(n-1+pos)/2;i++){//逆序pos后面的序列值
swap(&a[i],&a[n-1+pos-i]);
}
sort(a,n,b);//继续排下一个
}
int main()
{
int N;scanf("%d",&N);
int a[11]={0},stack[N],in[N],I=0,t;
while(scanf("%d",&t)!=EOF){
a[t]=1;
stack[I++]=t;//stack[]用于储存入站火车序号
}
t=0;
for(int i=1;i<11;i++){//为了优化最后排序的次数，in[]按序号大小存储入站火车号
if(a[i]){
in[t++]=i;
}
}
sort(in,N,stack);
}
执行耗时18ms，消耗内存328KB方法二：利用DFS遍历所有的合法情况，最后排序输出。（可以使用C库函数stdlib自带的qsort()排序）
因为是基于DFS，它是将一种情况或条件递归到尽头的办法。所以可以把问题对象转移为车站里是否有火车，可以分出3种情况：
1.如果站内还有火车，火车立刻出站，递归到站内没有火车，回溯；
2.如果还有火车没有进站，火车立刻进站，递归到所有火车都进站，回溯；
3.如果所有火车都曾进站，且站内没火车，此次递归结束，输出一个序列；
时间复杂度O(n!)，空间复杂度O(catalan(n))，排序时用到了卡特兰数大小的空间。
/*DFS迭代找出合法序列*/
#include <stdio.h>
#include <string.h>
int out_p=0;//out[]的指针，表明有多少火车已出站
int in_p=0;//in[]的指针，指向下一个入站火车
int stack_p=-1;//stack[]的指针，指向车站内的栈顶火车
int I=0;//记录合法序列个数
void dfs(int* a,int* b,int* c,int n,char d[][n]){
if(out_p==n){//递归出口：当火车全部出站，记录该合法序列
for(int i=0;i<n;i++){
d[I][i]=a[i]+'0';
}
I++;
return;
}
if(stack_p>-1){//递归场景1：如果站内还有火车，立刻出站，并使出站序列out_p++
a[out_p++]=b[stack_p--];//火车出站
dfs(a,b,c,n,d);
b[++stack_p]=a[--out_p];//回溯
}
if(in_p<n){//递归场景2：如果还有火车没有进站，立刻进站，并使stack_p++
b[++stack_p]=c[in_p++];//火车进站
dfs(a,b,c,n,d);
in_p--;stack_p--;//回溯
}
}
int partition(int n,char a[][n],int low,int high){//快排中确定基准序号
char* p=(char*)malloc(n);
for(int i=0;i<n;i++){//原字符串没有'\0'结束符，无法使用strcpy()函数
p[i]=a[low][i];
}
while(low<high){
while(low<high && strcmp(a[high],p)>=0){
high--;
}
for(int i=0;i<n;i++){
a[low][i]=a[high][i];
}
while(low<high && strcmp(a[low],p)<=0){
low++;
}
for(int i=0;i<n;i++){
a[high][i]=a[low][i];
}
}
for(int i=0;i<n;i++){
a[low][i]=p[i];
}
free(p);
return low;
}
void quicksort(int n,char a[][n],int low,int high){//快速排序
if(low<high){
int p=partition(n,a,low,high);
quicksort(n,a,low,p-1);
quicksort(n,a,p+1,high);
}
}
int catalan(n){//计算卡特兰数
long x1=1,x2=1;
for(int i=n;i>1;i--){
x1*=i;
}
for(int i=2*n;i>n;i--){
x2*=i;
}
x2/=x1*(n+1);
return x2;
}
int main(){
int N;scanf("%d",&N);
int NN=catalan(N);//计算有多少个合法序列
char legal[NN][N];//为所有的合法序列预先分配空间
int in[N],t,k=0;
while(scanf("%d",&t)!=EOF){
in[k++]=t;//in[]用于储存入站火车序号,即初始的序列
}
int out[N];//记录出站的火车序号
int stack[N];//记录正在站内等候的火车序号
dfs(out,stack,in,N,legal);//找出所有合法序列
quicksort(N,legal,0,NN-1);//排序
for(int i=0;i<NN;i++){
for(int j=0;j<N;j++){
printf("%c ",legal[i][j]);
}
printf("\n");
}
}
执行耗时5ms，消耗内存380KB
京公网安备 11010502036488号