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

Question

该设置类似于Knuth之前讨论的堆栈可排序排列问题，但是使用堆栈生成排列。我想编写一个程序来确定排列是否可以通过 2 个堆栈而不是仅 1 个堆栈生成堆栈。

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

1 到 n 的排列是堆栈生成的排列，当且仅 如果可以通过将 1 到 N 推到堆栈上并弹出它们来生成 ou000b.例如，堆栈生成的排列 （2， 1， 3） 可以是 通过执行操作生成 推送 1、推送 2、弹出、弹出、推送 3、弹出。

在这个问题中，我们不是只使用一个堆栈，而是使用两个堆栈： 每次您可以将元素推送到堆栈或弹出 元素，只要它是非空的。然而，一旦 元素被弹出，无法再次将其推回任一堆栈。

您的任务是确定是否可以通过以下方式生成排列 使用两个堆栈。

我知道如果排列包含模式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("Non");
            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("Yesn");
        } else {
            printf("Non");
        }
    }
    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("Yesn");
        } else {
            printf("Non");
        }
        reset();
    }
    return 0;
}