查找组和字母的组合

Question

我必须找到一组字母的组合，第一组中的第二个字母应该与第二组中的第一个字母相同等等

例如，这个组的解决方案：AA, CB, AC, BA, BD, DB 这是：CB, BD, DB, BA, AA, AC

到目前为止，我已经有了这段代码，它可以工作，但是如果有很多组，则需要很长时间才能计算出来。我需要让它更有效率。

在输入文件中，有这个输入

10
C D
B C
B B
B B
D B
B B
C A
A B
B D
D C

我的代码

#include <stdio.h>
#include <stdlib.h>

void permutation(char group[][2], int buffer, int sum) {
    int i, j;
    char temp;

    if (buffer == sum && group[1][1] == group[sum][2]) {
        for (i = 1; i < sum; i++)
            if (group[i][2] != group[i+1][1]) break;

        if (i == sum) {
            FILE *output;
            output = fopen("output.txt", "a");
            for (j = 1; j <= sum; j++) {
                fprintf(output, "%c %c\n", group[j][1], group[j][2]);
            }
            exit(1);
        }
    } else {
        for (i = buffer; i <= sum; i++) {
            temp = group[buffer][1];
            group[buffer][1] = group[i][1];
            group[i][1] = temp;
            temp = group[buffer][2];
            group[buffer][2] = group[i][2];
            group[i][2] = temp;

            permutation(group, buffer + 1, sum);

            temp = group[buffer][1];
            group[buffer][1] = group[i][1];
            group[i][1] = temp;
            temp = group[buffer][2];
            group[buffer][2] = group[i][2];
            group[i][2] = temp;
        }
    }
}

int main() {
    FILE *input;

    input = fopen("input.txt", "r");

    int sum, i;

    fscanf(input, "%d", &sum);

    char group[sum][2];

    for (i = 1; i <= sum; i++) {
        fscanf(input, "%s", &group[i][1]);
        fscanf(input, "%s", &group[i][2]);
    }

    permutation(group, 1, sum);
}

EDIT 所以我对我的程序做了一些修改（感谢你的帮助，我对编程很陌生所以我很抱歉有错误），我使用排列没有更多，我只是在寻找路径。它运行良好，但现在我的输入有 100000 个组，再次花费大量时间（大约 2 小时，我需要最多在 1 小时内完成）。我可能不得不再次以其他方式做到这一点 xD 有什么想法吗？

#include <stdio.h>

int find(char group[][2], int buffer, int sum, int path[]) {
    int i, j;

    for (i = 0; i < sum; i++) {
        for (j = 0; j < buffer; j++)
            if (path[j] == i)
                break;
        if (buffer == 0 ||
            (group[path[buffer-1]][1] == group[i][0] && buffer == j)) {
            printf("%d\n", buffer); // just for me to know what program is currently computing
            path[buffer] = i;
            find(group, buffer + 1, sum, path);
            if (path[sum-1] != 0)
                return;
        }
    }
}

int main() {
    FILE *input = fopen("input.txt", "r");

    if (input != NULL) {
        int sum, i;

        fscanf(input, "%d", &sum);
        char group[sum][2];
        int path[sum];

        for (i = 0; i < sum; i++)
            fscanf(input, " %c %c", &group[i][0], &group[i][1]);
        for (i = 0; i < sum;i++)
            path[i] = 0;

        find(group, 0, sum, path);

        FILE *output = fopen("output.txt", "a");
        for (i = 0; i < sum; i++)
            fprintf(output, "%c %c\n", group[path[i]][0], group[path[i]][1]);
    } else
        printf("Input file was not found.");
}

Answer 1

在 C 中，数组索引从 0 开始，因此大小为 N 的数组具有从 0 到 N-1 的有效索引。在上面的代码中，您正在越界访问数组 group，因为它的大小为 2（因此有效索引为 0 和 1），但您正在尝试访问索引 1 和 2.

要么改变：

char group[sum][2];

至：

char group[sum][3];

或使用索引 0/1 而不是 1/2.

另请注意，您的代码缺少错误检查，例如在 fopen.

的通话中

Answer 2

你的程序有几个问题：

您使用基于 1 的索引，这会导致混淆并导致引用数组和子数组超出其定义的末端。
您使用 %s 说明符使用 fscanf 解析输入：这是不安全的，将为您的每个输入写入 2 个字节，写入超出每个子数组的末尾和超出最后一个数组。

您已经知道如何解决这些问题，最好使用基于 0 的索引

您的算法非常无效，复杂O(n!)，因为您列举了所有可能的排列并仅检查完整排列的有效性。您可以通过仅枚举已经验证其初始元素约束的排列来显着提高性能。复杂度大大降低，仍然是二次方，但 n 非常小。

这是执行此操作的代码的修改版本：

#include <stdio.h>

int permutation(char group[][2], int buffer, int sum) {
    if (buffer == sum)
        return group[sum-1][1] == group[0][0];

    for (int i = buffer; i < sum; i++) {
        if (group[buffer-1][1] == group[i][0]) {
            char temp = group[buffer][0];
            group[buffer][0] = group[i][0];
            group[i][0] = temp;
            temp = group[buffer][1];
            group[buffer][1] = group[i][1];
            group[i][1] = temp;

            if (permutation(group, buffer + 1, sum))
                return 1;

            temp = group[buffer][0];
            group[buffer][0] = group[i][0];
            group[i][0] = temp;
            temp = group[buffer][1];
            group[buffer][1] = group[i][1];
            group[i][1] = temp;
        }
    }
    return 0;
}

int main(void) {
    FILE *input = fopen("input.txt", "r");
    int sum, i;

    if (input != NULL) {
        if (fscanf(input, "%d", &sum) != 1 || sum <= 0) {
            printf("invalid number of pairs\n");
            fclose(input);
            return 1;
        }

        char group[sum][2];

        for (i = 0; i < sum; i++) {
            if (fscanf(input, " %c %c", &group[i][0], &group[i][1]) != 2) {
                printf("incorrect input for pair number %d\n", i);
                fclose(input);
                return 1;
            }
        }
        fclose(input);
        if (permutation(group, 1, sum)) {
            FILE *output = fopen("output.txt", "a");
            if (output == NULL) {
                printf("cannot open output file\n");
                return 2;
            }
            for (i = 0; i < sum; i++) {
                fprintf(output, "%c %c\n", group[i][0], group[i][1]);
            }
            fclose(output);
            return 0;
        } else {
            printf("complete path not found\n");
            return 1;
        }
    }
    printf("cannot open input file\n");
    return 2;
}

我修改了代码的其他方面以提高效率和可重用性：

检查输入的有效性。
递归函数停止并且returns 1 找到完整路径。这允许程序继续它是否找到路径。
为了保持一致性，输出由 main 函数处理。

以上代码在我的笔记本电脑上 不到 0.002 秒 解决了指定输入 n=50 的问题。它打印 F C C E E F F E E E E E E E E E E B B F F E E A A F F C C A A A A E E F F C C E E E E E E E E E E B B C C E E E E F F E E F F F F E E C C E E E E E E B B F F A A D D A A C C C C E E E E E E B B D D F

EDIT 我意识到，由于您正在寻找一条完全封闭的路径，因此您无需为第一对尝试不同的可能性。 main 可以用 1 调用 permutation 而不是 0 并且 permutation 可以简化为 buffer 永远不会是 0。

Answer 3

您的新代码有一些问题：

find 被定义为 returning int，但你 return 什么都没有。你确实不测试你是否找到了一条完整的路径，完全依赖于至少有一个并且你已经找到它的假设。
您没有测试路径闭合。你可能偶然发现一条闭合路径，但也可能产生一条非闭合路径。
使用 2 个循环查找未使用的对的效率低于使用临时数组 used[sum]。
第一对永远是第一对，所以你可以稍微简化一下 find 函数。

这是一个改进的版本：

#include <stdio.h>

int find(char group[][2], int buffer, int sum, int path[], unsigned char used[]) {
    int i;
    char last = group[path[buffer-1]][1];

    if (buffer == sum)
        return last == group[0][0];

    for (i = 1; i < sum; i++) {
        if (!used[i] && last == group[i][0]) {
            path[buffer] = i;
            used[i] = 1;
            if (find(group, buffer + 1, sum, path, used))
                return 1;
            used[i] = 0;
        }
    }
    return 0;
}

int main() {
    FILE *input = fopen("input.txt", "r");

    if (input != NULL) {
        int sum = 0, i;

        fscanf(input, "%d", &sum);

        char group[sum][2];
        int path[sum];
        unsigned char used[sum];

        for (i = 0; i < sum; i++)
            fscanf(input, " %c %c", &group[i][0], &group[i][1]);

        path[0] = 0;  // always start at first element
        used[0] = 1;
        for (i = 1; i < sum; i++)
            used[i] = 0;

        if (find(group, 1, sum, path, used)) {
            FILE *output = fopen("output.txt", "a");
            for (i = 0; i < sum; i++)
                fprintf(output, "%c %c\n", group[path[i]][0], group[path[i]][1]);
        }
    } else {
        printf("Input file was not found.");
    }
    return 0;
}

编辑：我用你的大输入文件测试了这个新版本：它在我的笔记本电脑上崩溃了。具有 permutation 函数的先前版本非常有效，可在 0.060 秒内生成完整路径。所以有一个完整的路径，这个 find 函数有问题。

算法之间几乎没有区别：

permutation 使用更少的堆栈 space：一个大小为 n*2 (200k) 的自动数组对比 3 个自动数组总大小 n*(sizeof(int) + 3) (700k)。
permutation 使用较少的变量，因此递归使用较少的堆栈space，但两者可能使用超过 1 MB 的堆栈space 来递归 100000 次。
find 进行更多扫描，其中 permutation 交换 group 对并始终直接捕捉下一个。

我在没有递归的情况下重新实现了find，终于让它产生了一个完整的路径。它是不同的，计算时间更长，3.5 秒。

对于较大的输入文件，绝对不应该使用递归，甚至应该使用 malloc.

从堆中分配数组

下面是非递归代码，使用堆内存：

#include <stdio.h>
#include <stdlib.h>

int find(const char group[][2], int sum, int path[]) {
    path[0] = 0;
    if (sum <= 1)
        return group[0][1] == group[0][0];

    unsigned char *used = calloc((size_t)sum, sizeof(*used));

    for (int buffer = 1, i = 1;; i++) {
        if (i == sum) {
            --buffer;
            if (buffer == 0) {
                free(used);
                return 0;
            }
            i = path[buffer];
            used[i] = 0;
        } else
        if (!used[i] && group[path[buffer-1]][1] == group[i][0]) {
            path[buffer] = i;
            if (buffer == sum - 1) {
                if (group[i][1] == group[0][0]) {
                    free(used);
                    return 1;
                }
            } else {
                buffer++;
                used[i] = 1;
                i = 0;
            }
        }
    }
}

int main() {
    FILE *input = fopen("input.txt", "r");

    if (input != NULL) {
        int sum = 0, i;

        fscanf(input, "%d", &sum);

        char (*group)[2] = calloc((size_t)sum, sizeof(*group));
        int *path = calloc((size_t)sum, sizeof(*path));

        for (i = 0; i < sum; i++)
            fscanf(input, " %c %c", &group[i][0], &group[i][1]);

        if (find(group, sum, path)) {
            FILE *output = fopen("output.txt", "a");
            for (i = 0; i < sum; i++)
                fprintf(output, "%c %c\n", group[path[i]][0], group[path[i]][1]);
        }
    } else {
        printf("Input file was not found.");
    }
    return 0;
}

查找组和字母的组合

Find combination of groups and letters

c

combinations

permutation

letter