车皮编序问题 .
问题描述： 在一个列车调度站中，1 条轨道连接到1 条侧轨处，形成1 个铁路转轨栈，如下图所示。 其中左边轨道为车皮入口，右边轨道为出口，编号为1，2，…，n 的n 个车皮从入口依次进 入转轨栈，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1, a2,., an 。
编程任务 给定正整数n，编程计算左边轨道车皮编号依次为1，2，…，n 时，在右边轨道最多可 以得到多少个不同的车皮编序方案。 例如当n=3 时，最多得到5 组不同的编序方案如下：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1 .
数据输入： 由文件input.txt 给出输入数据。第一行有1 个正整数n，表示有n 个车皮。 .
结果输出: 将计算出的所有不同的编序方案，以及不同的编序方案数输出到文件output.txt 。文件 的每行是一个编序方案。文件的最后一行是编序方案数。
#include<iostream>
#include<stack>
using namespace std;
stack<int> s;
int count;
void swap(int &a,int &b)
{
int t = a;
a = b;
b = t;
}
//在全排列的基础上选择出合适的栈
void perm(int list[],int k,int m)
{
int i,j,flag;
if(k==m)
{
flag = 1;
for(i=1;i<=list[0];i++)
s.push(i);
// cout<<s.top()<<endl;
for(i=1;i<=m&&flag;i++)
{
//如果下一个数比当前的栈顶元素大，则应该进栈
if(s.top()<list[i])
{
for(j=s.top()+1;j<list[i];j++)
s.push(j);
}
//当栈顶元素比下一个数大的情况
else if(s.top()>list[i])
{//首先先出栈一个
s.pop();
//然后再和下一个数比较，如果两数之差大于1，则不满足堆栈情况，清空栈
if(s.top()-list[i]>=1)
{
flag = 0;
while(!s.empty())
{
s.pop();
}
}
}
}
//当满足堆栈时打印出所有
if(i>m)
{
count++;
for(i=0;i<=m;i++)
cout<<list[i]<<" " ;
cout<<endl;
}
}
else
{
for(i=k;i<=m;i++)
{ //交换位置
swap(list[k],list[i]);
//递归调用
perm(list,k+1,m);
//换回位置
swap(list[k],list[i]);
}
}
}
int main()
{
int a[100];
int n,i,j;
while(cin>>n)
{
//初始化个数为0
count=0;
for(i=0;i<n;i++)
a[i]=i+1;
perm(a,0,n-1);
cout<<count<<endl;
}
return 0;
}算法实验题 车皮编序问题（转化为在全排列的基础上的堆栈问题）,布布扣,bubuko.com
算法实验题 车皮编序问题（转化为在全排列的基础上的堆栈问题）
原文：http://blog.csdn.net/qq544529563/article/details/23715129