如何有效地编码/解码压缩的位置描述？

Question

我正在为日本象棋变体编写一个表库。为了索引表基数，我将每个国际象棋位置编码为整数。在编码步骤之一中，我对棋盘上棋子的位置进行编码。由于实际方法有点复杂，我就简单地解释一下这个问题。

\n

编码

\n

在残局桌面中，我有（比方说）六个不同的棋子，我想将它们分布在有 9 个方格的棋盘上。我可以 na\xc3\xafvely 用六元组 ( a , b , c , d , e , f \xe2\x80\x89 ) 表示它们的位置，其中每个变量a到f是 0 到 f 范围内的数字8 包括指示相应棋子所在位置的位置。

\n

然而，这种表示并不是最佳的：没有两个棋子可以占据同一个方格，但前面提到的编码很高兴地允许这样做。我们可以通过六元组 [ a, b', c', d', e', f' \xe2\x80\x89] 编码相同的位置，其中a与之前的a相同， b'是来自0 到 7（含），表示第二块所在方格的编号。这是通过为第一块不在的每个方格分配一个从 0 到 7 的数字来实现的。例如，如果第一块在方格 3 上，则第二块的方格数为：

\n

1st piece: 0 1 2 3 4 5 6 7 8\n2nd piece: 0 1 2 - 3 4 5 6 7\n

\n

其他部分的编码类似，c'为0到6的数字，d'为0到5的数字等。例如na\xc3\xafve编码(5, 2, 3, 0, 7, 4 ) 产生紧凑编码 (5, 2, 2, 0, 3, 1)：

\n

1st: 0 1 2 3 4 5 6 7 8 --> 5\n2nd: 0 1 2 3 4 - 5 6 7 --> 2\n3rd: 0 1 - 2 3 - 4 5 6 --> 2\n4th: 0 1 - - 2 - 3 4 5 --> 0\n5th: - 0 - - 1 - 2 3 4 --> 3\n6th: - 0 - - 1 - 2 - 3 --> 1\n

\n

在我的实际编码中，我要编码的片数是不固定的。然而，棋盘上的格子数量是。

\n

问题

\n

如何有效地将 na\xc3\xafve 表示形式转换为紧凑表示形式，反之亦然？我使用标准 C99 来编写该程序。在这个问题的上下文中，我对使用非标准构造、内联汇编或内在函数的答案不感兴趣。

\n

问题澄清

\n

由于这个问题似乎有些混乱：

\n

\n
• 问题是找到一种实用有效的方法来实现na\xc3\xafve和紧凑位置表示之间的转换
\n
• 两种表示形式都是特定范围内整数的n元组。问题不在于如何将这些表示编码为其他内容。
\n
• 在我遇到的一种情况下，方格数为 25，块数最多为 12。但是，我对适用于合理参数空间的实现感兴趣（例如，最多 64 个方格和最多 32 个块） 。
\n
• 我对替代表示或编码不感兴趣，尤其是不是最佳的表示或编码。
\n
• 我对紧凑表示不值得付出努力的言论也不感兴趣。
\n

\n

Answer 1

我找到了一个更优雅的解决方案，使用 64 位整数，使用单个循环进行编码和解码，最多可处理 16 个位置：

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

void encode16(int dest[], int src[], int n) {
    unsigned long long state = 0xfedcba9876543210;
    for (int i = 0; i < n; i++) {
        int p4 = src[i] * 4;
        dest[i] = (state >> p4) & 15;
        state -= 0x1111111111111110 << p4;
    }
}

void decode16(int dest[], int src[], int n) {
    unsigned long long state = 0xfedcba9876543210;
    for (int i = 0; i < n; i++) {
        int p4 = src[i] * 4;
        dest[i] = (state >> p4) & 15;
        unsigned long long mask = ((unsigned long long)1 << p4) - 1;
        state = (state & mask) | ((state >> 4) & ~mask);
    }
}

int main(int argc, char *argv[]) {
    int naive[argc], compact[argc];
    int n = argc - 1;

    for (int i = 0; i < n; i++) {
        naive[i] = atoi(argv[i + 1]);
    }

    encode16(compact, naive, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", compact[i]);
    }
    printf("\n");

    decode16(naive, compact, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", naive[i]);
    }
    printf("\n");
    return 0;
}

该代码使用 64 位无符号整数来保存 16 个值范围内的数组0..15。这样的数组可以一步并行更新，提取值很简单，删除值稍微麻烦一些，但仍然只需几步。

您可以使用不可移植的 128 位整数（__int128gcc 和 clang 都支持类型）将此方法扩展到 25 个位置，利用 的事实对每个位置进行 5 位编码，5 * 25 < 128但神奇常量编写起来更加麻烦。