Função de emparelhamento - Pairing function

Em matemática , uma função de emparelhamento é um processo para codificar exclusivamente dois números naturais em um único número natural.

Qualquer função de emparelhamento pode ser usada na teoria dos conjuntos para provar que números inteiros e racionais têm a mesma cardinalidade que os números naturais.

Definição

Uma função de emparelhamento é uma bijeção

${\ displaystyle \ pi: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N}.}$

Mais geralmente, uma função de emparelhamento em um conjunto A é uma função que mapeia cada par de elementos de A em um elemento de A , de modo que quaisquer dois pares de elementos de A sejam associados a diferentes elementos de A, ou uma bijeção de para A . ${\ displaystyle A ^ {2}}$

Função de emparelhamento de Hopcroft e Ullman

Hopcroft e Ullman (1979) definem a seguinte função de emparelhamento:, onde . ${\ displaystyle <i, j>: = {\ frac {1} {2}} (i + j-2) (i + j-1) + i}$${\ displaystyle i, j \ in \ {1,2,3, \ dots \}}$

Função de emparelhamento Cantor

A função de emparelhamento Cantor atribui um número natural a cada par de números naturais

A função de emparelhamento Cantor é uma função de emparelhamento recursiva primitiva

${\ displaystyle \ pi: \ mathbb {N} \ times \ mathbb {N} \ to \ mathbb {N}}$

definido por

${\ displaystyle \ pi (k_ {1}, k_ {2}): = {\ frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2}}$

onde . ${\ displaystyle k_ {1}, k_ {2} \ in \ {0,1,2,3, \ dots \}}$

Também pode ser expresso como . ${\ displaystyle Par [x, y]: = {\ frac {x ^ {2} + 3x + 2xy + y + y ^ {2}} {2}}}$

Também é estritamente monotônico em cada argumento, isto é, para todos , se , então ; da mesma forma, se , então . ${\ displaystyle k_ {1}, k_ {1} ', k_ {2}, k_ {2}' \ in \ mathbb {N}}$${\ displaystyle k_ {1} <k_ {1} '}$${\ displaystyle \ pi (k_ {1}, k_ {2}) <\ pi (k_ {1} ', k_ {2})}$${\ displaystyle k_ {2} <k_ {2} '}$${\ displaystyle \ pi (k_ {1}, k_ {2}) <\ pi (k_ {1}, k_ {2} ')}$

A afirmação de que esta é a única função de emparelhamento quadrático é conhecida como teorema de Fueter-Pólya . Se esta é a única função de emparelhamento polinomial, ainda é uma questão em aberto. Quando se aplicar a função de emparelhamento para k ₁ e k ₂ , muitas vezes, denotam o número resultante como ⟨ K ₁ , K ₂ ⟩ .

Esta definição pode ser generalizada indutivamente para a função de tupla de Cantor

${\ displaystyle \ pi ^ {(n)}: \ mathbb {N} ^ {n} \ to \ mathbb {N}}$

para como ${\ displaystyle n> 2}$

${\ displaystyle \ pi ^ {(n)} (k_ {1}, \ ldots, k_ {n-1}, k_ {n}): = \ pi (\ pi ^ {(n-1)} (k_ { 1}, \ ldots, k_ {n-1}), k_ {n})}$

com o caso base definido acima para um par: ${\ displaystyle \ pi ^ {(2)} (k_ {1}, k_ {2}): = \ pi (k_ {1}, k_ {2}).}$

Inverter a função de emparelhamento Cantor

Let Ser um número natural arbitrário. Mostraremos que existem valores únicos, tais que ${\ displaystyle z \ in \ mathbb {N}}$${\ displaystyle x, y \ in \ mathbb {N}}$

${\ displaystyle z = \ pi (x, y) = {\ frac {(x + y + 1) (x + y)} {2}} + y}$

e, portanto, esse π é invertível. É útil definir alguns valores intermediários no cálculo:

${\ displaystyle w = x + y \!}$

${\ displaystyle t = {\ frac {1} {2}} w (w + 1) = {\ frac {w ^ {2} + w} {2}}}$

${\ displaystyle z = t + y \!}$

onde t é o número do triângulo de w . Se resolvermos a equação quadrática

${\ displaystyle w ^ {2} + w-2t = 0 \!}$

para w em função de t , obtemos

${\ displaystyle w = {\ frac {{\ sqrt {8t + 1}} - 1} {2}}}$

que é uma função estritamente crescente e contínua quando t é real não negativo. Desde a

${\ displaystyle t \ leq z = t + y <t + (w + 1) = {\ frac {(w + 1) ^ {2} + (w + 1)} {2}}}$

nós entendemos isso

${\ displaystyle w \ leq {\ frac {{\ sqrt {8z + 1}} - 1} {2}} <w + 1}$

e assim

${\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor.}$

onde ⌊ ⌋ é a função de piso . Assim, para calcular x e y de z , que fazemos:

${\ displaystyle w = \ left \ lfloor {\ frac {{\ sqrt {8z + 1}} - 1} {2}} \ right \ rfloor}$

${\ displaystyle t = {\ frac {w ^ {2} + w} {2}}}$

${\ displaystyle y = zt \!}$

${\ displaystyle x = wy. \!}$

Uma vez que a função de emparelhamento Cantor é invertível, deve ser um para um e para .

Exemplos

Para calcular π (47, 32) :

47 + 32 = 79 ,

79 + 1 = 80 ,

79 × 80 = 6320 ,

6320 ÷ 2 = 3160 ,

3160 + 32 = 3192 ,

então π (47, 32) = 3192 .

Para encontrar x e y tais que π ( x , y ) = 1432 :

8 × 1432 = 11456 ,

11456 + 1 = 11457 ,

√ 11457 = 107,037 ,

107,037 - 1 = 106,037 ,

106,037 ÷ 2 = 53,019 ,

⌊53,019⌋ = 53 ,

então w = 53 ;

53 + 1 = 54 ,

53 × 54 = 2862 ,

2862 ÷ 2 = 1431 ,

então t = 1431 ;

1432 - 1431 = 1 ,

então y = 1 ;

53 - 1 = 52 ,

então x = 52 ; assim, π (52, 1) = 1432 .

Derivação

Uma função "sinuosa" que aumenta diagonalmente, a partir dos mesmos princípios da função de emparelhamento de Cantor, é freqüentemente usada para demonstrar a contabilidade dos números racionais.

A forma gráfica da função de emparelhamento de Cantor, uma progressão diagonal, é um truque padrão no trabalho com sequências infinitas e contabilidade . As regras algébricas desta função diagonal podem verificar sua validade para uma gama de polinômios, dos quais um quadrático acabará sendo o mais simples, usando o método de indução . Na verdade, essa mesma técnica também pode ser seguida para tentar derivar qualquer número de outras funções para qualquer variedade de esquemas de enumeração do plano.

A função de emparelhamento pode geralmente ser definida indutivamente - isto é, dado o n º par, o que é o ( n + 1) th par? A forma como a função de Cantor progride diagonalmente ao longo do plano pode ser expressa como

${\ displaystyle \ pi (x, y) + 1 = \ pi (x-1, y + 1)}$.

A função também deve definir o que fazer quando atinge os limites do primeiro quadrante - a função de emparelhamento de Cantor é redefinida para o eixo x para retomar sua progressão diagonal um passo adiante, ou algebricamente:

${\ displaystyle \ pi (0, k) + 1 = \ pi (k + 1,0)}$.

Também precisamos definir o ponto de partida, qual será o passo inicial em nosso método de indução: π (0, 0) = 0 .

Suponha que haja um polinômio bidimensional quadrático que pode se ajustar a essas condições (se não houvesse, pode-se apenas repetir tentando um polinômio de grau mais alto). A forma geral é então

${\ displaystyle \ pi (x, y) = ax ^ {2} + por ^ {2} + cxy + dx + ey + f}$.

Conecte nossas condições iniciais e de contorno para obter f = 0 e:

${\ displaystyle bk ^ {2} + ek + 1 = a (k + 1) ^ {2} + d (k + 1)}$,

para que possamos combinar nossos k termos para obter

b = a

d = 1- a

e = 1+ a .

Portanto, todos os parâmetros podem ser escritos em termos de a, exceto c , e temos uma equação final, nosso passo diagonal, que os relacionará:

${\ displaystyle {\ begin {alinhados} \ pi (x, y) + 1 & = a (x ^ {2} + y ^ {2}) + cxy + (1-a) x + (1 + a) y + 1 \ \ & = a ((x-1) ^ {2} + (y + 1) ^ {2}) + c (x-1) (y + 1) + (1-a) (x-1) + ( 1 + a) (y + 1). \ End {alinhado}}}$

Expanda e combine os termos novamente para obter valores fixos para a e c e, portanto, todos os parâmetros:

a = 1/2= b = d

c = 1

e =3/2

f = 0 .

Portanto

${\ displaystyle {\ begin {align} \ pi (x, y) & = {\ frac {1} {2}} (x ^ {2} + y ^ {2}) + xy + {\ frac {1} { 2}} x + {\ frac {3} {2}} y \\ & = {\ frac {1} {2}} (x + y) (x + y + 1) + y, \ end {alinhado}} }$

é a função de emparelhamento de Cantor, e também demonstramos através da derivação que esta satisfaz todas as condições de indução.

Outras funções de emparelhamento

A função é uma função de emparelhamento. ${\ displaystyle P_ {2} (x, y): = 2 ^ {x} (2y + 1) -1}$

Em 1990, Regan propôs a primeira função de emparelhamento conhecida que é computável em tempo linear e com espaço constante (como os exemplos anteriormente conhecidos só podem ser computados em tempo linear se a multiplicação também pode ser , o que é duvidoso). Na verdade, essa função de emparelhamento e seu inverso podem ser calculados com transdutores de estado finito que funcionam em tempo real. No mesmo artigo, o autor propôs duas funções de emparelhamento mais monótonas que podem ser calculadas online em tempo linear e com espaço logarítmico ; o primeiro também pode ser calculado offline com espaço zero.

Em 2001, Pigeon propôs uma função de emparelhamento baseada na intercalação de bits , definida recursivamente como:

${\ displaystyle <i, j> _ {P} = {\ begin {cases} T {\ text {if}} i = j = 0; \\ <\ lfloor i / 2 \ rfloor, \ lfloor j / 2 \ rfloor> _ {P}: i_ {0}: j_ {0} {\ text {caso contrário,}} \ end {cases}}}$

onde e são os bits menos significativos de i e j, respectivamente. ${\ displaystyle i_ {0}}$${\ displaystyle j_ {0}}$

Em 2006, Szudzik propôs uma função de emparelhamento "mais elegante" definida pela expressão que pode ser desemparelhada usando a expressão . (Qualitativamente, ele atribui números consecutivos aos pares ao longo das bordas dos quadrados.) Esta função de emparelhamento ordena as expressões de cálculo do combinador SK por profundidade. ${\ displaystyle ElegantPair [x, y]: = {\ begin {cases} y ^ {2} + x {\ text {if}} x \ neq \ max \ {x, y \} \\ x ^ {2} + x + y {\ text {if}} x = \ max \ {x, y \} \\\ end {cases}},}$${\ displaystyle ElegantUnpair [z]: = {\ begin {cases} \ {z- \ lfloor {\ sqrt {z}} \ rfloor ^ {2}, \ lfloor {\ sqrt {z}} \ rfloor \} {\ texto {if}} z- \ lfloor {\ sqrt {z}} \ rfloor ^ {2} <\ lfloor {\ sqrt {z}} \ rfloor \\\ {\ lfloor {\ sqrt {z}} \ rfloor, z- \ lfloor {\ sqrt {z}} \ rfloor ^ {2} - \ lfloor {\ sqrt {z}} \ rfloor {\ text {if}} z- \ lfloor {\ sqrt {z}} \ rfloor ^ {2} \ geq \ lfloor {\ sqrt {z}} \ rfloor \} \ end {cases}}}$

Notas

Referências