当前位置:网站首页>Fundamentals of programming stack shuffling

Fundamentals of programming stack shuffling

2020-11-13 00:31:17 Sandy rabbit

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

Return to category : All articles >> Basic knowledge of

Return to the superior : Programming based - Stack (Stack)



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 & \to & m_0=1 \\ n=1 & \to & m_1=1 \\ n=2 & \to & m_2=2 \\ n=3 & \to & m_3=5 \\ \vdots & \to & \vdots \\ n & \to & m_n \end{array} n=0n=1n=2n=3nm0=1m1=1m2=2m3=5mn

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 n=0 , m 0 = 1 m_0=1 m0=1 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 m 0 × m 2 = 1 m_0 \times m_2 = 1 m0×m2=1
    1 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 n = 0 n=0 n=0 , m 0 = 1 m_0=1 m0=1 m 1 × m 1 = 1 m_1 \times m_1 = 1 m1×m1=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 m2=m0×m1+m1×m0=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 n=0 , m 0 = 1 m_0=1 m0=1 n = 2 n=2 n=2 , m 2 = 2 m_2=2 m2=2 m 0 × m 2 = 2 m_0 \times m_2 = 2 m0×m2=2
    1 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 m 1 × m 1 = 1 m_1 \times m_1 = 1 m1×m1=1
    2 n = 2 n=2 n=2 , m 2 = 2 m_2=2 m2=2 n = 0 n=0 n=0 , m 0 = 1 m_0=1 m0=1 m 2 × m 0 = 2 m_2 \times m_0 = 2 m2×m0=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 m3=m0×m2+m1×m1+m2×m0=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 n=0 , m 0 = 1 m_0=1 m0=1 n = 3 n=3 n=3 , m 3 = 5 m_3=5 m3=5 m 0 × m 3 = 5 m_0 \times m_3 = 5 m0×m3=5
    1 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 n = 2 n=2 n=2 , m 2 = 2 m_2=2 m2=2 m 1 × m 2 = 2 m_1 \times m_2 = 2 m1×m2=2
    2 n = 2 n=2 n=2 , m 2 = 2 m_2=2 m2=2 n = 1 n=1 n=1 , m 1 = 1 m_1=1 m1=1 m 2 × m 1 = 2 m_2 \times m_1 = 2 m2×m1=2
    3 n = 3 n=3 n=3 , m 3 = 5 m_3=5 m3=5 n = 0 n=0 n=0 , m 0 = 1 m_0=1 m0=1 m 3 × m 0 = 5 m_3 \times m_0 = 5 m3×m0=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 m4=m0×m3+m1×m2+m2×m1+m3×m0=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 mn=m0×mn1+m1×mn2++mn2×m1+mn1×m0

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} mn=n+11(2nn)=n+11C2nn

Tips: Cartland number reference link
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 .


版权声明
本文为[Sandy rabbit]所创,转载请带上原文链接,感谢

随机推荐