Eu quero codificar compactamente números inteiros positivos xem bits, de uma maneira que permita a decodificação de volta nos números inteiros originais para um decodificador sem estado, sabendo o valor máximo mde cada um x; deve ser possível decodificar exclusivamente a concatenação de codificações, como é o caso da codificação de Huffman.
_{[A introdução acima motiva o resto, mas não faz parte da definição formal]}

Notação: para qualquer número inteiro não negativo i, n(i)seja o número de bits necessário para representar iem binário; esse é o menor inteiro não negativo de ktal forma quei>>k == 0

  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..

Eu quero uma função F(x,m)definida para 0<xe x<=m, com saída, uma sequência de ' 0' ou ' 1', com estas propriedades:

1. F(x,m)tem comprimento menor que 2*n(x)ou 2*n(m)-1, o que for menor.
2. Se x<yentão:
   • F(x,m)não é mais do que F(y,m);
   • F(x,m)e F(y,m)diferem em alguma posição ao longo de F(x,m);
   • há um 0na F(x,m)primeira posição.
3. Quando por certas mpropriedades 1 e 2 não se definir de forma única F(x,m)para todos positivos xno máximo m, se rejeitar qualquer codificação dando um mais F(x,m)do que alguns codificação de outro modo aceitável, para a mais pequena xpara que o comprimento não coincidem.

Nota: No exemplo acima, implicitamente, 0<x, 0<y, 0<m, x<=m, e y<=m, de modo que F(x,m)e F(y,m)são definidos.

É solicitado o programa mais curto que, dado qualquer um xe matendendo às restrições acima e até 9 dígitos decimais, gera uma F(x,m)consistência com as regras acima. A seguinte estrutura C (ou seu equivalente em outros idiomas) não é contada:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line

Comentário: A propriedade 1 limita agressivamente o comprimento codificado; a propriedade 2 formaliza que a decodificação inequívoca é possível e canoniza a codificação; Afirmo (sem prova) que isso é suficiente para definir exclusivamente a saída de Fquando m+1é uma potência de dois e que a propriedade 3 é suficiente para definir exclusivamente Fpara outra m.

Aqui está uma tabela parcial (artesanal; a primeira versão postada estava cheia de erros, desculpe):

  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

Python 3, 163 bytes

n=int.bit_length
R=range
def F(x,m,c=0):
 for i in R(x):L=2*n(m)-2;D=1<<L;r=n(D-c-sum(D>>min(2*n(x+1)-1,L)for x in R(i+1,m)))-1;v=c;c+=1<<r
 return bin(v)[2:L+2-r]

Ignore o c=0parâmetro, isso é um truque de golfe.

Isso avidamente escolhe a menor representação possível para cada número, desde que os números restantes ainda sejam representáveis. Portanto, por construção, satisfaz exatamente as propriedades desejadas. Na verdade, não é tão difícil modificar esse código para suportar um conjunto diferente de regras de codificação, como resultado.

Por exemplo, aqui estão as saídas até m=15:

m\x |   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
----+----------------------------------------------------------------------------------------------------------------------------
1   |   
2   |   0       1
3   |   0       10      11
4   |   0       10      110     111
5   |   0       10      110     1110    1111
6   |   0       100     101     110     1110    1111
7   |   0       100     101     1100    1101    1110    1111
8   |   0       100     101     110     11100   11101   11110   11111
9   |   0       100     101     110     11100   11101   11110   111110  111111
10  |   0       100     101     1100    1101    11100   11101   11110   111110  111111
11  |   0       100     101     1100    1101    11100   11101   111100  111101  111110  111111
12  |   0       100     101     1100    11010   11011   11100   11101   111100  111101  111110  111111
13  |   0       100     101     1100    11010   11011   11100   111010  111011  111100  111101  111110  111111
14  |   0       100     101     11000   11001   11010   11011   11100   111010  111011  111100  111101  111110  111111
15  |   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111

Python, 171

def F(x,m):
 a=0;b=[9]
 while len(b)<m:
    if 4**len(bin(len(b)))*2>64*a<4**len(bin(m)):
     if(a&a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

Observe que as linhas que parecem começar com 4 espaços na verdade começam com uma guia.

Teste, com o script de teste do bitpwner:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)   0       
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      110      11100    11101    11110    11111   
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111  
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111  

Explicação:

Tudo isso se baseia na observação de que, entre dois elementos consecutivos do código, F (x, m) e F (x + 1, m), sempre adicionamos um ao número binário e depois multiplicamos por dois algumas vezes. Se essas etapas forem seguidas, é um código válido. O restante simplesmente testa para garantir que seja curto o suficiente.

Golfe: 175 -> 171: alterado 2 ** (2 * ... para 4 **

Python - 370

Cria uma árvore de huffman, equilibra-a de acordo com as regras e, em seguida, percorre a árvore para obter os valores finais.

def w(n,m,c,p=""):
    try:[w(n[y],m,c,p+`y`)for y in 1,0]
    except:c[n[0]]=p
d=lambda x:len(x)>1and 1+d(x[1])
v=lambda x,y:v(x[1],y-1)if y else x
def F(x,m):
    r=[m];i=j=0
    for y in range(1,m):r=[[m-y],r]
    while d(r)>len(bin(m))*2-6-(m==8):g=v(r,i);g[1],g[1][0]=g[1][1],[g[1][0],g[1][1][0]];i,j=[[i+1+(d(g)%2<1&(1<i<5)&(m%7<1)),j],[j+1]*2][d(g)<5]
    c={};w(r,m,c);return c[x]

Para uma solução mais sucinta baseada no padrão emergente, observe a resposta de isaacg.
É um bom exemplo de como uma abordagem completamente diferente pode resolver o problema.

Teste:

chars = 8
maxM = 15
print " "*chars,
for m in range(1,maxM+1):
    p = `m`
    print p+" "*(chars-len(p)),
print
for m in range(1,maxM+1):
    p = "F(x,"+`m`+")"
    print p+" "*(chars-len(p)),
    for x in range(1,maxM+1):
        try:
            q = `F(x,m)`[1:-1]
            print q+" "*(chars-len(q)),
        except:
            print
            break

Resultados:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)           
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      1100     1101     1110     11110    11111   
F(x,9)   0        100      101      1100     1101     1110     11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      11000    11001    11010    11011    11100    11101    11110    111110   111111  
F(x,13)  0        100      101      11000    11001    11010    11011    11100    11101    111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111