整数置换的表示形式 [英] representation of permutation of integer in bits
问题描述
我试图表示给定正整数N的排列.
例如.代表数字1-16的任意排列，每个数字使用4位或更少.
这个想法是，我们可以用16位8 * 4 + 4 * 3 + 2 * 2 + 1 * 1 = 49位而不是64位来表示置换.
我有一个示例数据集，如下所示[10 1 3 11 2 12 8 7 4 6 9 13 15 16 5 14].
我尝试了以下c程序来实现此目的，但是我不确定如何在 C 程序中使用向量来存储给定整数的位置.
我有这个问题:
如果整数的范围是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);
}
}
上面的代码显示了以下输出，我不确定它是否正确.
元素10在位置数组中的位置是:0
元素1在位置数组中的位置是:1
元素3在位置数组中的位置是:2
元素11在位置数组中的位置是:3
元素2在位置数组中的位置是:4
元素12在位置数组中的位置是:5
元素8在位置数组中的位置是:6
元素7在位置数组中的位置是:7
元素4在位置数组中的位置是:8
元素6在位置数组中的位置是:9
元素9在位置数组中的位置是:10
元素13在位置数组中的位置是:11
元素15在位置数组中的位置是:12
元素16在位置数组中的位置是:13
元素5在位置数组中的位置是:14
元素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
对于实现此任务的任何帮助或建议，我将不胜感激.
Lehmer编码似乎是您实现目标的途径.
(感谢Ian Abbott提供的技术术语.)
此时，您可以将范围的第一个数字始终编码为可能数字中的索引，取4位.无需猜测所需的位数，始终为4.
然后将下一个数字编码为剩余可能数字中的索引(因为第一个数字将不会重复)，即仅15个数字中的一个；仍然是4位.
当只剩下8个数字时，所需的编码位数最终下降到3，而仅剩下4个可能的数字则降至2，在最后两个可能的数字之间进行选择时需要1，而实际上对最后一个可能的数字进行编码需要0. /p>
那将是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
I am trying to represent the permutation of N given positive integers.
E.g. represent an arbitrary permutation of the numbers 1-16 using 4 bits or less for each of the numbers.
The idea is that we can represent the permutation of 16 in 8*4 + 4*3 + 2*2 + 1*1 = 49 bits instead of 64 bits.
I have an example data set as follows [10 1 3 11 2 12 8 7 4 6 9 13 15 16 5 14].
I have tried the following c program to achieve this but I am not sure how to use vector in C program to store the position of given integers.
I have this problem:
If the integers range fro 1-16, then what would be stored in the position[0] as I need to compute further.
The following is the piece of code that I have used:
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);
}
}
The above code is showing the following output which I am not sure whether it is correct or not.
the position of element 10 in position array is: 0
the position of element 1 in position array is: 1
the position of element 3 in position array is: 2
the position of element 11 in position array is: 3
the position of element 2 in position array is: 4
the position of element 12 in position array is: 5
the position of element 8 in position array is: 6
the position of element 7 in position array is: 7
the position of element 4 in position array is: 8
the position of element 6 in position array is: 9
the position of element 9 in position array is: 10
the position of element 13 in position array is: 11
the position of element 15 in position array is: 12
the position of element 16 in position array is: 13
the position of element 5 in position array is: 14
the position of element 14 in position array is: 15
the value for Q is :1
the value for Q is :3
the value for Q is :1
the value for Q is :5
the value for Q is :10
the value for Q is :5
the value for Q is :4
the value for Q is :3
the value for Q is :3
the value for Q is :0
the value for Q is :1
the value for Q is :1
the value for Q is :1
the value for Q is :3
the value for Q is :1
I will appreciate for any kind of help or suggestion to achieve this task.
The Lehmer encoding seems to be the path to your goal.
(Thanks to Ian Abbott for providing the technical term.)
You can encode the first number of the range ALWAYS as the index among the possible numbers at this point, taking 4 bits. No need to guess the number of needed bits, it is always 4.
Then encode the next number as the index among the remaining possible numbers (since the first will not be repeated), i.e. one among only 15; still 4 bits.
The needed amount of bits to encode finally drops to 3 when only 8 numbers are left, to 2 when only 4 possible numbers are left, 1 for the choice between the last two possible numbers and actually 0 bits to encode the last possible number.
That would be 8*4 + 4*3 + 2*2 + 1*1 + 1*0 = 49.
E.g.
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
The number of needed bits for encoding is always 49: 4*8+3*4+2*2+1+0.
Always 4 bits for the first 8 numbers,
always 3 bits for the next 4 numbers,
always 2 bits for the next 2 numbers,
always 1 bit for the next to last and
always 0 bits for the last number.
Note, I just discovered Ians comment with interesting link to Lehmer code.
I think it is what I describe above.
I changed the first part of your code to get the encoding right.
I did not understand the second part of your code, the one showing the Q values.
#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]);
}
}
Output:
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
这篇关于整数置换的表示形式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
