# Fundamentals of programming stack shuffling

2020-11-13 00:31:17

# Programming based - The application of the stack - Mixed washing (Stack Shuffling)

## 1 Brief introduction of mixed washing

“ Mixed washing ” The original idea is to reshuffle the cards .

In the shuffle of the stack , Suppose the element is 1 To n, The stack order is also 1 To n, The answer to these questions may be needed in the application ：

• （1） How many possibilities are there in the outbound sequence ？

• （2） Find out all the stacks （ Push ） Sequence .

• （3） Give a stack sequence , Ask the minimum stack capacity ？

• （4） Give a （ Or more ） Stack out sequence , Ask if the sequence is （ Which sequence is not ） The original sequence was mixed and washed ？

After that, we mainly have questions （1） And questions （2） The solution of , The code will use C++.

## 2 How many possibilities are there in the outbound sequence ？

In the case of a small number of elements , We can write the order of their stack , for example ：

• The number of elements is 2 when , The stack sequence is [1, 2], The stack order is ：

• [1, 2]： Enter into 1、 Out 1、 Enter into 2、 Out 2
• [2, 1]： Enter into 1, Enter into 2, Out 2, Out 1
• The number of elements is 3 when , The stack order is [1, 2, 3], The stack order is ：

• [1, 2, 3]： Enter into 1, Out 1, Enter into 2, Out 2, Enter into 3, Out 3
• [1, 3, 2]： Enter into 1, Out 1, Enter into 2, Enter into 3, Out 3, Out 2
• [2, 1, 3]： Enter into 1, Enter into 2, Out 2, Out 1, Enter into 3, Out 3
• [2, 3, 1]： Enter into 1, Enter into 2, Out 2, Enter into 3, Out 3, Out 1
• [3, 2, 1]： Enter into 1, Enter into 2, Enter into 3, Out 3, Out 2, Out 1

Empathy , You can write the number of elements as 4 The stack order of time .

With these , We can observe the law , Deduce the stack order of more elements .

Be careful ： Element number 0 when , Yes 1 Sort out the stack order （ empty ）. Element number 1 when , There is also only 1 Sort out the stack order （ Namely 1 In itself ）

Let's say the number of elements is n, The stack out sequence has m Kind of , be ：

（ Tips ： Formula in CSDN Of app There may be garbled code in , Please open ）

n = 0 → m 0 = 1 n = 1 → m 1 = 1 n = 2 → m 2 = 2 n = 3 → m 3 = 5 ⋮ → ⋮ n → m n \begin{array}{cc} n=0 &amp; \to &amp; m_0=1 \\ n=1 &amp; \to &amp; m_1=1 \\ n=2 &amp; \to &amp; m_2=2 \\ n=3 &amp; \to &amp; m_3=5 \\ \vdots &amp; \to &amp; \vdots \\ n &amp; \to &amp; m_n \end{array}

Let's take the first element （ namely 1） To do the derivation ：

• When n by 2 when , Elements 1 Out of the stack Subscript by [0, 1]

Elements 1 The location of The number of stack out sequences on the left side The number of stack out sequences on the right side Total number of sequences
0 n = 0 n=0 , m 0 = 1 m_0=1 n = 1 n=1 , m 1 = 1 m_1=1 m 0 × m 2 = 1 m_0 \times m_2 = 1
1 n = 1 n=1 , m 1 = 1 m_1=1 n = 0 n=0 , m 0 = 1 m_0=1 m 1 × m 1 = 1 m_1 \times m_1 = 1

This is the number of stack out sequences 2 The sum of the positions , namely ： m 2 = m 0 × m 1 + m 1 × m 0 = 2 m_2 = m_0 \times m_1 + m_1 \times m_0 = 2

• When n by 3 when , Elements 1 Out of the stack Subscript by [0, 1, 2]

Elements 1 The location of The number of stack out sequences on the left side The number of stack out sequences on the right side Total number of sequences
0 n = 0 n=0 , m 0 = 1 m_0=1 n = 2 n=2 , m 2 = 2 m_2=2 m 0 × m 2 = 2 m_0 \times m_2 = 2
1 n = 1 n=1 , m 1 = 1 m_1=1 n = 1 n=1 , m 1 = 1 m_1=1 m 1 × m 1 = 1 m_1 \times m_1 = 1
2 n = 2 n=2 , m 2 = 2 m_2=2 n = 0 n=0 , m 0 = 1 m_0=1 m 2 × m 0 = 2 m_2 \times m_0 = 2

This is the number of stack out sequences 3 The sum of the positions , namely ： m 3 = m 0 × m 2 + m 1 × m 1 + m 2 × m 0 = 5 m_3 = m_0 \times m_2 + m_1 \times m_1 + m_2 \times m_0 = 5

• When n by 4 when , Elements 1 Out of the stack Subscript by [0, 1, 2, 3]

Elements 1 The location of The number of stack out sequences on the left side The number of stack out sequences on the right side Total number of sequences
0 n = 0 n=0 , m 0 = 1 m_0=1 n = 3 n=3 , m 3 = 5 m_3=5 m 0 × m 3 = 5 m_0 \times m_3 = 5
1 n = 1 n=1 , m 1 = 1 m_1=1 n = 2 n=2 , m 2 = 2 m_2=2 m 1 × m 2 = 2 m_1 \times m_2 = 2
2 n = 2 n=2 , m 2 = 2 m_2=2 n = 1 n=1 , m 1 = 1 m_1=1 m 2 × m 1 = 2 m_2 \times m_1 = 2
3 n = 3 n=3 , m 3 = 5 m_3=5 n = 0 n=0 , m 0 = 1 m_0=1 m 3 × m 0 = 5 m_3 \times m_0 = 5

This is the number of stack out sequences 4 The sum of the positions , namely ： m 4 = m 0 × m 3 + m 1 × m 2 + m 2 × m 1 + m 3 × m 0 = 14 m_4 = m_0 \times m_3 + m_1 \times m_2 + m_2 \times m_1 + m_3 \times m_0 = 14

In the same way, we can get ：

m n = m 0 × m n − 1 + m 1 × m n − 2 + ⋯ + m n − 2 × m 1 + m n − 1 × m 0 m_n = m_0 \times m_{n-1} + m_1 \times m_{n-2} + \cdots + m_{n-2} \times m_1 + m_{n-1} \times m_0

This is typical Carter LAN number （Catalan Number） The formula , namely ：

m n = 1 n + 1 ( 2 n n ) = 1 n + 1 C 2 n n m_n = \frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} = \frac{1}{n+1} C_{2n}^{n}

See the following link for the detailed derivation process and description of catteland number ：
Wikipedia(en): Catalan number
Baidu Encyclopedia ： Carter LAN number

## 3 Find out all the stacks （ Push ） Sequence （C++ Code）

This means that every element has to be pushed into a stack , And they all have to make a stack .

### 3.1 The header file main.h

We need header files （main.h）：

#pragma once

#include <vector> //  Vector list
#include <stack> //  Stack


### 3.2 Main function file main.cpp

This is the recursive function we need ：

//  Calculate all outbound sequences （ Subscript from 0 Calculation ）
// params:
//      length:      Number of stack elements
//      outputs:     Output all output sequence results （ Subscript ）
void Shuffling(int length, vector<vector<int>> &outputs)
{

if (length <= 0)
{

return;
}

stack<int> inStack; //  Stack sequence
vector<int> outList; //  Stack out sequence

Internal_ShufflingRecursion(length, 0, inStack, outList, outputs); //  Recursive solution
}

//  Internal calculation recursion
// params:
//      length:      Number of stack elements
//      index:       Current element subscript
//      inStack:     Current stack sequence
//      outList:     Current stack sequence
//      outputs:     All output stack sequence results （ Subscript ）
void Internal_ShufflingRecursion(int length,
int index,
stack<int> &inStack,
vector<int> &outList,
vector<vector<int>> &outputs)
{

//  If all elements are out of the stack
if (outList.size() == length)
{

outputs.push_back(outList); //  Add it to the result outputs in
return;
}

//  If the current element subscript is less than the total number of elements , Start stack recursion
if (index < length)
{

inStack.push(index); //  Stack current subscript
Internal_ShufflingRecursion(length, index + 1, inStack, outList, outputs);
inStack.pop(); //  Top of stack element
}

//  If the number of stack elements is greater than 0, Start stack recursion
if (inStack.size() > 0)
{

int top = inStack.top(); //  Get the stack top element subscript
inStack.pop(); //  Top of stack element
outList.push_back(top); //  Add the stack out element to the stack out sequence

//  Recursion here , When the judgment element is out of the stack , Whether there is a need for stack in and stack out operation （ Is there any element that hasn't been added to the stack ）
Internal_ShufflingRecursion(length, index, inStack, outList, outputs);

inStack.push(top); //  Re stack the original stack top element
outList.pop_back(); //  Remove the original stack top element
}
}


And finally, our main function ：

#include "main.h"

#include <iostream>
using namespace std;

void Shuffling(int length, vector<vector<int>> &outputs);
void Internal_ShufflingRecursion(int length,
int index,
stack<int> &inStack,
vector<int> &outList,
vector<vector<int>> &outputs);

int main()
{

int length = -1;

while (true)
{

cout << " Mixed washing of the stack , Please enter the stack length ：";
while (!(cin >> length) || length < 0)
{

cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << " Illegal input , Please re-enter the stack length ：";
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');

vector<vector<int>> outputs; //  Define all outbound results
Shuffling(length, outputs); //  Calculate the stack sequence

//  Print all out of stack order
for (int i = 0; i < outputs.size(); i++)
{

cout << i << ": ";
for (int j = 0; j < outputs[i].size(); j++)
{

//  The result is subscript from 0 Start , The element is from 1 Start
//  If the raw data is not 1-n
//  Replace here with  Original stack sequence [outputs[i][j]]
cout << (outputs[i][j] + 1) << " ";
}
cout << endl;
}
cout << " Altogether " << outputs.size() << " Grow stack sequence ." << endl;
cout << endl;
}

system("pause");
return 0;
}


If you need a push sequence , Only need to outputs The reverse output of each sequence in .

### 3.3 Running results

 Mixed washing of the stack , Please enter the stack length ：3
0: 3 2 1
1: 2 3 1
2: 2 1 3
3: 1 3 2
4: 1 2 3
Altogether 5 Grow stack sequence .

Mixed washing of the stack , Please enter the stack length ：4
0: 4 3 2 1
1: 3 4 2 1
2: 3 2 4 1
3: 3 2 1 4
4: 2 4 3 1
5: 2 3 4 1
6: 2 3 1 4
7: 2 1 4 3
8: 2 1 3 4
9: 1 4 3 2
10: 1 3 4 2
11: 1 3 2 4
12: 1 2 4 3
13: 1 2 3 4
Altogether 14 Grow stack sequence .