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

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

编码

在残局桌面中，我有（比方说）六个不同的棋子，我想将它们分布在有 9 个方格的棋盘上。我可以天真地用六元组来表示他们的立场（a, b, c, d, e, f) 其中每个变量a to f是 0 到 8（含）范围内的数字，表示相应棋子所在的位置。

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

1st piece: 0 1 2 3 4 5 6 7 8
2nd piece: 0 1 2 - 3 4 5 6 7

其他部分的编码类似，c'作为 0 到 6 之间的数字，d'作为从 0 到 5 的数字等。例如，朴素编码 (5, 2, 3, 0, 7, 4) 产生紧凑编码 (5, 2, 2, 0, 3, 1)：

1st: 0 1 2 3 4 5 6 7 8 --> 5
2nd: 0 1 2 3 4 - 5 6 7 --> 2
3rd: 0 1 - 2 3 - 4 5 6 --> 2
4th: 0 1 - - 2 - 3 4 5 --> 0
5th: - 0 - - 1 - 2 3 4 --> 3
6th: - 0 - - 1 - 2 - 3 --> 1

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

问题

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

问题澄清

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

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

我找到了一个更优雅的解决方案，使用 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 位整数将此方法扩展到 25 个位置（类型__int128gcc 和 clang 均支持），利用以下事实对每个位置进行 5 位编码：5 * 25 < 128，但是神奇的常量写起来比较麻烦。