# Dictionary order sorting [permutation] + train entry and exit stations

[Description]
Given a positive integer N representing the number of trains, 0 < N < 10, then enter the train inbound sequence, a total of N trains, each train numbered 1-9 numbers. It is required to sort out the serial number of the outbound train in lexicographic order.
[Input]
There are several groups of test cases, each group of first line input a positive integer N (0 < N < 10), the second line includes N positive integers, ranging from 1 to 9.
[Output]
Output the train outbound serial number sorted in lexicographic order, each number separated by spaces, and each output sequence line, specifically sample.
Sample input 3123
Sample output
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

[Thoughts on Problem Solving]

Firstly, all possible output sequences are constructed.

Then: output in dictionary order

Initialize a sort vector < string >: Each output is stored in the vector in string form, and then sort the vector in dictionary order.

```#include <stack>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>

using namespace std;

bool isOutNum(int *push, int *pop, int len)//Judging whether pop is the stack-out sequence of push
{
if (push == NULL || pop == NULL || len <= 0)
return false;
stack<int> Stack;
int i = 0, j = 0;
for (i = 0;i<len;i++)//push the numbers on the stack in turn
{
Stack.push(push[i]);
while (j<len && Stack.size() != 0 && pop[j] == Stack.top())//Determine in turn whether each pop sequence value is equal to the top of the stack
{
Stack.pop();
j++;
}
}
return Stack.empty();
}

int main()
{
int N;
while (cin >> N)
{
//Initialize arrays
int *pushNum = new int[N];
int *popNum = new int[N];

for (int i = 0;i<N;i++)
{
cin >> pushNum[i];
popNum[i] = pushNum[i];
}
//pop is an ordered arrangement
sort(popNum, popNum + N);// This is because it's a continuous pointer interval.

vector<int> vec(N);//Initialize a vector;
for (size_t i = 0; i < vec.size(); i++)
{
vec[i] = popNum[i]; //To assign values from pop to vec, use a loop
}

do
{
if (isOutNum(pushNum, popNum, N))//If the arrangement is correct, the output
{
for (int i = 0;i<N - 1;i++)
cout << popNum[i] << " ";
cout << popNum[N - 1] << endl;
}
} while (next_permutation(popNum, popNum + N));//Get the next permutation
}
return 0;
}
```

Added by Hotkey on Tue, 08 Oct 2019 07:41:20 +0300