在全排列的基础上生成拉丁方为什么不对?

x23hi9b5
  • 5
新手上路,请多包涵


拉丁方阵是一种 n × n 的方阵,在这种 n × n 的方阵里,恰有 n 种不同的元素,每一种不同的元素在同一行或同一列里只出现一次。
3阶的拉丁放应该只有上面12个。我的方法是先生产全排列,固定行,再判断列,但得到的结果并不对,请问应该怎么更正呢?

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

#define N 3

unsigned int factorial(unsigned int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

int perm_arr[][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
int A[][3];
int count = 0;

int ok(int *A, int *B) {
    for (int i = 0; i < N; ++i) {
        if (A[i] == B[i])
            return 0;
    }
    return 1;
}

void dfs(int level) {
    if (level == (N)) {
        count++;
    } else
        for (int i = 0; i < factorial(N); i++) {
            int flag = 1;
            for (int j = 0; j < level; ++j) {
                if (ok(A[j], perm_arr[i])) {
                    flag = 0;
                    break;
                }
            }
            if (flag) {
                memcpy(A[level], perm_arr[i], N * sizeof(int));
                dfs(level + 1);
            }
        }
}

int main() {
    dfs(0);
    printf("count = %d\n", count);
    return 0;
}
回复
阅读 336
1 个回答

第一个问题

int perm_arr[][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
int A[][3];

perm_arr 这么定义没问题,因为后面有初始化的参数,编译器会计算[]的大小,但 int A[][3]就有问题了,因为后面并没有初始化参数,这个定义就等于 int* A[3],后面的 memcpy 会导致程序崩溃。

第二个问题,你的递归代码试图在生成全排列的同时做检测,这样是不行的,因为你没有检测前面的行。我把改的代码写在这里,你可以参考一下

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

#define N 3

unsigned int factorial(unsigned int n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

int perm_arr[][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
int A[3][3];
int count = 0;

int ok(int *A, int *B) {
    for (int i = 0; i < N; ++i) {
        if (A[i] == B[i])
            return 0;
    }
    return 1;
}

void dfs(int level) {
    if (level == (N)) {
        for (int i=0;i<N;i++)
        {
            for (int j=i+1;j<N;j++)
            {
                if (!ok(A[i], A[j]))
                    return;
            }
        }
        count++;
    } else
        for (int i = 0; i < factorial(N); i++) {
            memcpy(A[level], perm_arr[i], N * sizeof(int));
            dfs(level + 1);
        }
}

int main() {
    dfs(0);
    printf("count = %d\n", count);
    return 0;
}
你知道吗?

宣传栏