确定排列是否可以由 2 个并行堆栈生成的算法

Question

设置类似于Knuth之前讨论的stack-sortable permutation problem，但是是在用stack生成排列。我想编写一个程序来确定排列是否可通过 2 个堆栈而非仅 1 个堆栈生成。

这其实是一道作业题，要求如下：

A permutation of 1 to n is a stack-generated permutation if and only if it can be generated by pushing 1 to n onto a stack and popping them o. For example, stack-generated permutation (2, 1, 3) can be generated by doing operations push 1, push 2, pop, pop, push 3, pop.

In this problem, instead of using only one stack, we use two stacks: every time you can push an element to either stack, or you can pop element from either stack as long as it is non-empty. However, once an element is popped, it cannot be pushed back to either stack again.

Your task is to determine whether a permutation can be generated by using two stacks.

我知道如果排列包含模式 4123，则无法生成。但是，进行模式匹配似乎非常耗时并且可能超出我的能力，更不用说我不知道 4123 是否是唯一的模式。

目前我正在尝试用2个堆栈实际生成它以确定是否可以生成排列，但我的算法只能确定一些堆栈可生成的排列。因此我想知道这个问题的正确算法是什么。一个有效的 C 代码当然会很棒，但任何提示、建议或伪代码也足够好。谢谢！

要确定的示例排列：

62 61 58 53 67 66 47 65 69 68 64 45 70 71 63 44 42 60 72 59 41 73 74 57 56 39 55 54 38 37 52 51 50 49 48 76 46 43 75 40 36 35 77 34 31 30 33 29 32 78 22 79 28 27 80 20 26 25 24 23 83 82 81 85 84 87 89 21 19 90 88 92 86 95 94 18 98 96 97 93 17 15 99 91 16 100 14 12 13 9 8 11 6 5 10 7 4 3 2 1

我目前的实现（很乱，没有注释，不建议大家阅读）：

#include <stdio.h>

#define MAXSIZE 1000

typedef struct stack {
    int data[MAXSIZE];
    int top;
} Stack;


void push(Stack *s, int d);

int pop(Stack *s);

int peek(Stack *s);

int isEmpty(Stack *s);

int getPos(int d[], int size, int a);

void push(Stack *s, int d) {
    (*s).top++;
    (*s).data[(*s).top] = d;

}


int pop(Stack *s) {
    int d = (*s).data[(*s).top];
    (*s).top--;
    return d;
}

int peek(Stack *s) {
    if (!isEmpty(s)) {
        return (*s).data[(*s).top];
    } else return -1;
}

int isEmpty(Stack *s) {
    if ((*s).top < 0) {
        return 1;
    } else return 0;
}


int getPos(int d[], int size, int a) {
    int i = 0, al = -1;
    for (i = 0; i < size; i++) {
        if (d[i] == a) {
            al = i;
        }


    }
    if (al != -1) {
        return al;

    } else return -1;

}


int main() {
    int t = 0;
    scanf("%d", &t);
    int i = 0;
    for (i = 0; i < t; i++) {
        int failed = 0;
        int n = 0;
        scanf("%d", &n);
        int target[MAXSIZE];
        int j = 0;
        for (j = 0; j < n; j++) {
            scanf("%d", &target[j]);
        }
        Stack s1, s2;
        s1.top = -1;
        s2.top = -1;

        Stack *s1_ptr = &s1;
        Stack *s2_ptr = &s2;

        int output[MAXSIZE];
        int oh = 0;
        int th = 0;
        int k = 1;
        for (k = 1; k <= n; k++) {

            int f1 = 0, f2 = 0;
            int checkAgain = 1, pushed = 0;

            while (checkAgain) {
                checkAgain = 0;

                if (k == target[th]) {
                    push(s1_ptr, k);
                    output[oh] = pop(s1_ptr);
                    oh++;
                    th++;
                    pushed = 1;

                } else if (!isEmpty(s1_ptr) && peek(s1_ptr) == target[th]) {
                    output[oh] = pop(s1_ptr);
                    oh++;
                    th++;
                    checkAgain = 1;

                } else if (!isEmpty(s2_ptr) && peek(s2_ptr) == target[th]) {
                    output[oh] = pop(s2_ptr);
                    oh++;
                    th++;
                    checkAgain = 1;

                }
            }
            if (!pushed) {
                if (isEmpty(s1_ptr)) {
                    push(s1_ptr, k);
                } else if (isEmpty(s2_ptr)) {
                    push(s2_ptr, k);
                } else {
                    int s1l = -1, s2l = -1;
                    if (peek(s1_ptr) >= 0) {
                        s1l = getPos(target, n, peek(s1_ptr));
                    }
                    if (peek(s2_ptr) >= 0) {
                        s2l = getPos(target, n, peek(s2_ptr));
                    }
                    int kl = getPos(target, n, k);
                    int canPush1 = 0, canPush2 = 0;

                    if (kl < s1l) {

                        canPush1 = 1;
                    }
                    if (kl < s2l) {

                        canPush2 = 1;
                    }
                    if (canPush1 && canPush2) {
                        if (s1l < s2l) {
                            push(s1_ptr, k);
                        } else {
                            push(s2_ptr, k);
                        }
                    } else if (canPush1 && !canPush2) {
                        push(s1_ptr, k);
                    } else if (!canPush1 && canPush2) {
                        push(s2_ptr, k);
                    } else {
                        failed = 1;
                        break;
                    }
                }
            }
        }

        if (failed) {
            printf("No\n");
            continue;
        }

        int m = th;
        for (m = th; m < n; m++) {
            if (peek(s1_ptr) == target[th]) {
                output[oh] = pop(s1_ptr);
                oh++;
                th++;

            } else if (peek(s2_ptr) == target[th]) {
                output[oh] = pop(s2_ptr);
                oh++;
                th++;

            } else {
                failed = 1;
                break;
            }
        }

        if (th == n) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }

    }

    return 0;
}

Answer 1

我在两个中文站点的帮助下解决了它，因为NOIP2008中实际上有一个类似的问题，它处理可按2个堆栈排序的排列。可生成排列的解决方案非常相似。如果有人对解决方案感兴趣，我可以稍后再写。

对我有帮助的两个站点：

NOIP2008 双栈排序 twostack 题解

NOIP2008提高组复赛题解

我的解决方案：

#include <stdio.h>
#include <string.h>

#define MAXN 1002
int const NEINF = -1;

int targetPermutation[MAXN];
int precalculatedMax[MAXN];
int bipartiteGraph[MAXN];
int adjacencyMatrix[MAXN][MAXN];
int N;
int noSolution = 0;

void reset();

void colouringAndCheckConflict(int i, int c);

void checkAdjacencyAndDye();

void colouringAndCheckConflict(int i, int c) {
    bipartiteGraph[i] = c;
    int j;
    for (j = 1; j <= N; j++) {
        if (adjacencyMatrix[i][j]) {
            if (bipartiteGraph[j] == c) //conflict : not a bipartite graph
            {
                noSolution = 1;
                return;
            }
            if (!bipartiteGraph[j]) {
                colouringAndCheckConflict(j, 3 - c); // color the opposite color 1<->2
            }
        }
    }
}

void checkAdjacencyAndDye() {
    /* 231 for sortable
     * i<j<k, S[k]<S[i]<S[J]
     * 312 for generatable
     * k<i<j, S[i]<S[J]<S[k]
     * DONE: Modify the algorithm to make it right for generation instead of sortable
    */
    int i, j;
    precalculatedMax[0] = NEINF;
    for (i = 1; i <= N; i++) {
        precalculatedMax[i] = targetPermutation[i];
        if (precalculatedMax[i - 1] > precalculatedMax[i])
            precalculatedMax[i] = precalculatedMax[i - 1];
    }
    for (i = 1; i <= N - 1; i++) {
        for (j = i + 1; j <= N; j++) {
            if (targetPermutation[i] < targetPermutation[j] && precalculatedMax[i - 1] > targetPermutation[j]) {
                adjacencyMatrix[i][j] = adjacencyMatrix[j][i] = 1;
            }
        }
    }
    for (i = 1; i <= N; i++) {
        if (!bipartiteGraph[i] && !noSolution) {
            colouringAndCheckConflict(i, 1);
        }
    }
}

void reset() {
    memset(adjacencyMatrix, 0, sizeof(adjacencyMatrix));
    memset(bipartiteGraph, 0, sizeof(bipartiteGraph));
    memset(targetPermutation, 0, sizeof(targetPermutation));
    memset(precalculatedMax, 0, sizeof(precalculatedMax));
    N = 0;
    noSolution = 0;
}

int main() {

    int t;
    scanf("%d", &t);
    int k;
    for (k = 1; k <= t; k++) {


        int i;
        scanf("%d", &N);
        for (i = 1; i <= N; i++) {
            scanf("%d", &targetPermutation[i]);

        }
        checkAdjacencyAndDye();
        if (!noSolution) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
        reset();
    }

    return 0;
}

确定排列是否可以由 2 个并行堆栈生成的算法

Algorithm to determine whether a permutation can be generated by 2 parallel stacks

c

algorithm

permutation