c - 以位表示整数的排列

Question

我试图表示 N 个给定正整数的排列。
例如。表示数字 1-16 的任意排列，每个数字使用 4 位或更少。

想法是我们可以用 8*4 + 4*3 + 2*2 + 1*1 = 49 位而不是 64 位来表示 16 的排列。
我有一个示例数据集如下 [10 1 3 11 2 12 8 7 4 6 9 13 15 16 5 14]。

我尝试了以下 c 程序来实现这一点，但我不确定如何在 C 程序中使用 vector 来存储给定整数的位置。

我有这个问题:
如果整数范围从 1 到 16，那么我需要进一步计算时将存储在 position[0] 中的内容。

下面是我用过的一段代码:

void main()
{
    int position[16];// a vector
    int buffer[16] = {10, 1,3, 11, 2, 12, 8, 7, 4, 6, 9, 13, 15, 16, 5, 14};
    int buffer_copy[16];// copy of original buffer 

    int i, j;
    for (i=0; i<16; i++)
    {
          buffer_copy[i]=buffer[i];
    }     

    for(i=0; i<16; i++)
    {
         position[buffer[i]]= i;
         printf("\n the position of element %d in position array is: %d",
                 buffer[i], position[buffer[i]]);
    }

     int next = 8;
     for (i =1; i<16; i++)
     {
        int pos, q=0;
        pos = position[i];

       // **To check the number of positions unchecked between 0 and pos.**
        for (j=0; j<pos; j++)
        {
            if(buffer_copy[j]>=0)
            {
                q=q+1;
            }
            buffer_copy[pos] =-1;
        }
        printf("\n the value for Q is :%d", q);
     }
}

上面的代码显示了以下输出，我不确定它是否正确。

position数组中元素10的位置为:0
位置数组中元素1的位置为:1
position数组中元素3的位置为:2
position数组中元素11的位置为:3
position数组中元素2的位置为:4
position数组中元素12的位置为:5
position数组中元素8的位置为:6
position数组中元素7的位置为:7
position数组中元素4的位置为:8
position数组中元素6的位置为:9
position数组中元素9的位置为:10
position数组中元素13的位置为:11
position数组中元素15的位置为:12
position数组中元素16的位置为:13
position数组中元素5的位置为:14
position数组中元素14的位置为:15
Q 的值为 :1
Q 的值为 :3
Q 的值为 :1
Q 的值为 :5
Q 的值为:10
Q 的值为 :5
Q 的值为 :4
Q 的值为 :3
Q 的值为 :3
Q 的值为 :0
Q 的值为 :1
Q 的值为 :1
Q 的值为 :1
Q 的值为 :3
Q 的值为:1

对于完成此任务的任何帮助或建议，我将不胜感激。

Answer 1

Lehmer 编码似乎是您实现目标的途径。
(感谢 Ian Abbott 提供技术术语。)

您可以将范围的第一个数字 ALWAYS 编码为此时可能数字中的索引，占用 4 位。无需猜测所需位数，它始终是 4。
然后将下一个数字编码为剩余可能数字中的索引(因为第一个不会重复)，即只有 15 个中的一个；仍然是 4 位。
当只剩下 8 个数字时，编码所需的位数最终下降到 3，当只剩下 4 个可能的数字时下降到 2，1 用于在最后两个可能的数字之间进行选择，而实际上 0 位来编码最后一个可能的数字。

那就是 8*4 + 4*3 + 2*2 + 1*1 + 1*0 = 49。

例如

1,16,3,8,11,13,7,2,4,5,6,12,15,14,9,10

 1, index  0 among 16 possibles (1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,16): 0000
16, index 14 among 15 possibles (_,2,3,4,5,6,7,8,9,A,B,C,D,E,F,16): 1110
 3, index  1 among 14 possibles (_,2,3,4,5,6,7,8,9,A,B,C,D,E,F,_) : 0001
 8, index  5 among 13 possibles (_,2,_,4,5,6,7,8,9,A,B,C,D,E,F,_) : 0101
11, index  7 among 12 possibles (_,2,_,4,5,6,7,_,9,A,B,C,D,E,F,_) : 0111
13, index  8 among 11 possibles (_,2,_,4,5,6,7,_,9,A,_,C,D,E,F,_) : 1000
 7, index  4 among 10 possibles (_,2,_,4,5,6,7,_,9,A,_,C,_,E,F,_) : 0100
 2, index  0 among  9 possibles (_,2,_,4,5,6,_,_,9,A,_,C,_,E,F,_) : 0000
 4, index  0 among  8 possibles (_,_,_,4,5,6,_,_,9,A,_,C,_,E,F,_) : 000
 5, index  0 among  7 possibles (_,_,_,_,5,6,_,_,9,A,_,C,_,E,F,_) : 000
 6, index  0 among  6 possibles (_,_,_,_,_,6,_,_,9,A,_,C,_,E,F,_) : 000
12, index  2 among  5 possibles (_,_,_,_,_,_,_,_,9,A,_,C,_,E,F,_) : 010
15, index  3 among  4 possibles (_,_,_,_,_,_,_,_,9,A,_,_,_,E,F,_) : 11
14, index  2 among  3 possibles (_,_,_,_,_,_,_,_,9,A,_,_,_,E,_,_) : 10
 9, index  0 among  2 possibles (_,_,_,_,_,_,_,_,9,A,_,_,_,_,_,_) : 0
10, only one remaning, no encoding

编码需要的位数总是49:4*8+3*4+2*2+1+0。
前 8 个数字总是 4 位，
接下来的 4 个数字总是 3 位，
接下来的 2 个数字总是 2 位，
倒数第二个和
总是1位 最后一个数字总是 0 位。

请注意，我刚刚发现 Ians 评论中包含指向 Lehmer 代码的有趣链接。
我想这就是我上面描述的。

我更改了您代码的第一部分以使编码正确。
我不明白你代码的第二部分，即显示 Q 值的部分。

#include <stdio.h>

void main(void)
{
    int position[16];// a vector
    int buffer[16] = {10, 1,3, 11, 2, 12, 8, 7, 4, 6, 9, 13, 15, 16, 5, 14};
    int buffer_copy[16];// copy of original buffer

    int i, j;
    for (i=0; i<16; i++)
    {
          buffer_copy[i]=i;
    }

    for(i=0; i<16; i++)
    {    int pos=0;
         for(j=0; j<16; j++)
         {
             if(buffer_copy[j]==0)
             { /* nothing */
             } else if (buffer_copy[j]==buffer[i])
             {
                 buffer_copy[j]=0;
                 break;
             } else
             {
                 pos++;
             }
         }
         position[i]=pos;

         printf("\n the index of '%2d' among the remaining numbers is: %d",
                 buffer[i], position[i]);
    }

}

输出:

 the index of '10' among the remaining numbers is: 9
 the index of ' 1' among the remaining numbers is: 0
 the index of ' 3' among the remaining numbers is: 1
 the index of '11' among the remaining numbers is: 7
 the index of ' 2' among the remaining numbers is: 0
 the index of '12' among the remaining numbers is: 6
 the index of ' 8' among the remaining numbers is: 4
 the index of ' 7' among the remaining numbers is: 3
 the index of ' 4' among the remaining numbers is: 0
 the index of ' 6' among the remaining numbers is: 1
 the index of ' 9' among the remaining numbers is: 1
 the index of '13' among the remaining numbers is: 1
 the index of '15' among the remaining numbers is: 2
 the index of '16' among the remaining numbers is: 2
 the index of ' 5' among the remaining numbers is: 0
 the index of '14' among the remaining numbers is: 0