algs4 1.3.46栈可生成性问题中禁止出现的排列

本文主要是介绍algs4 1.3.46栈可生成性问题中禁止出现的排列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 代码：

#include <stack>
#include <iostream>
#include <vector>
#include <random>
#include <time.h>

using std::cout;
using std::stack;
using std::vector;
using std::default_random_engine;
using std::uniform_int_distribution;


void GenerateRandomSeqence(int size, vector<int> &out)
{
    default_random_engine e;
    uniform_int_distribution<int> id(0, 20);

    e.seed(time(nullptr));
    cout << time(nullptr) << "\n";
    for (int i = 0; i < size; i++)
    {
        out.push_back(id(e));
    }
}

bool CanGenerateStack(vector<int> &sequence)
{
    int top = sequence.size() - 1;
    for (int i = top; i > 1; i--)
    {
        int minIndex = i;
        int curHead = sequence[i];
        for (int j = top - 1; j >= 0; j--)
        {
            if (sequence[j] >= curHead)
            {
                continue;
            }

            if (sequence[j] > sequence[minIndex])
            {
                cout << "a: " << sequence[minIndex] << ", b: " << sequence[j] << ", c: " << curHead << "\n";
                return false;
            }
            else 
            {
                minIndex = j;
            }
        }
    }
    return true;
}

void PrintVector(const vector<int> &sequence)
{
    for (auto &&v : sequence)
    {
        cout << v << " ";
    }
    cout << "\n";
}

int main()
{
    const int SEQUENCE_SIZE = 5;
    vector<int> sequence(SEQUENCE_SIZE);

    GenerateRandomSeqence(SEQUENCE_SIZE, sequence);
    PrintVector(sequence);
    bool ret = CanGenerateStack(sequence);
    cout << (ret ? "CanGenerate" : "CanNotGenerate") << "\n";
    return 0;
}

• 运行结果

run 10 times !
=================== 1 ==================
1641409646
5 5 8 14 11 
CanGenerate
=================== 2 ==================
1641409647
5 8 3 2 1 
CanGenerate
=================== 3 ==================
1641409648
5 11 19 12 13 
CanGenerate
=================== 4 ==================
1641409649
5 13 14 1 3 
a: 1, b: 13, c: 14
CanNotGenerate
=================== 5 ==================
1641409650
5 16 9 10 14 
CanGenerate
=================== 6 ==================
1641409651
5 19 4 20 4 
a: 4, b: 19, c: 20
CanNotGenerate
=================== 7 ==================
1641409652
5 1 20 9 15 
a: 1, b: 5, c: 15
CanNotGenerate
=================== 8 ==================
1641409653
5 4 14 18 6 
a: 4, b: 5, c: 6
CanNotGenerate
=================== 9 ==================
1641409654
5 6 9 7 17 
a: 7, b: 9, c: 17
CanNotGenerate
=================== 10 ==================
1641409655
5 9 4 16 7 
a: 4, b: 5, c: 7
CanNotGenerate

这篇关于algs4 1.3.46栈可生成性问题中禁止出现的排列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！