representation of permutation of integer in bits

Question

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.

Answer 1

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