Teste se existe um inteiro k para adicionar uma sequência para torná-lo uma subsequência de outra seqüência

Question

suponha que sequência $ a $ a $ contém $ n $ inteiros $ a_1, A_2, A_3, \ LDOTs, A_n $ e sequência $ B $ contém $ m $ inteiros $ B_1, B_2, B_3, \ LDOTS, B_M $ . Sabemos que $ m \ GEQ N $ . Assumimos sem perda de generalidade que sequences $ a $ e $ B $ são classificados em ordem crescente.

Qual é o algoritmo mais rápido para determinar se existe um inteiro $ k $ tal que a sequência $ a_1 + k, A_2 + K, A_3 + K, \ LDOTs, A_N + K $ é uma subsequência da seqüência $ B $ ?

Aqui está um algoritmo ingênuo, que levaria $ o (n (m-n)) $ tempo. Armazene a sequência $ B $ como hashtable. Para cada elemento $ b_j $ da $ B $ (exceto a maior matemática $ n $ elementos), use $ b_j-a_1 $ como seu palpite em $ k $ ; Você pode verificar esse palpite, verificando se cada uma das $ a_1 + k, \ pontos, A_n + k $ estão na hashtable $ B $ . Isso leva $ o (n) $ tempo esperado por adivinha em $ k $ , e você faz $ mn $ Adivinha, então, no total, o tempo de execução esperado é $ o (n (mn)) $ . Podemos fazer melhor?

Eu me deparei com este problema ao tentar combinar duas imagens binárias (testando se uma imagem contém a outra).

Answer 1

Aqui está uma heurística que nem sempre funciona, mas deve trabalhar com alta probabilidade se os números inteiros nas matrizes são escolhidos aleatoriamente de um espaço grande o suficiente.

Inicialize um hashtable de contagens $ c $ para todos os zeros. Em seguida, repita $ t $ vezes: selecione aleatoriamente $ i, j $ , compute $ b_j-a_i $ e incremento $ c [B_J-A_I] $ . Finalmente, classifique $ c $ por conta, da maior contagem para menor; Então, para cada um dos maiores valores da $ c [k '] $ , tente $ k' $ como seu palpite na $ k $ e verifique cada palpite.

Observe que, em cada iteração, a probabilidade de incrementar $ c [k] $ é pelo menos $ 1 / m $ ; Considerando que se se $ l \ ne k $ , esperamos $ c [l] $ para ser incrementado muito mais raramente (assumindo que os inteiros nas matrizes são aleatórios e grandes o suficiente). Assim, depois de $ t $ iterations, esperamos $ \ mathbb {e} [c [k]] \ ge t / m $ mas $ \ mathbb {e} [c [l]] \ ll t / m $ . Então, uma vez $ t $ é grande o suficiente, $ c [k] $ deve ser maior que todos os outros entrada em $ c $ .

Quão grande faz $ t $ precisa ser? Eu espero que $ T= O (m \ log m) $ deve ser suficiente, com base em uma aproximação da teorema de limite central para a conta $ C [l] $ , supondo que estamos dispostos a aceitar uma pequena probabilidade de erro (que pode ser conduzido exponencialmente pequeno). O fator constante oculto pela notação Big-O pode ser não-trivial.

Esta é apenas uma heurística, e haverá certamente insumos onde falhar.

Answer 2

Aqui está um algoritmo em execução em $ \ mathcal {o} (n \ sqrt {n} + m \ log m) $ tempo.

Deixe $ W $ denotar a função que para inteiro $ t $ , conta o número de pares que sua diferença é $ t $ : $ w (t)=lirt {(x, y): x \ em A, y \ in b, yx= t \} \ rVer $ . Se tivéssemos acesso a $ w (t) $ nós poderíamos simplesmente encontrar o máximo e ver se é $ n $ ou não. A ideia principal é estimar $ W $ usando a transformação rápida de Fourier. Se os números forem limitados, ele produzirá a solução exata, caso contrário, pode-se usar o módulo para um número suficientemente grande e, em seguida, verificar as soluções quando forem encontradas.

Deixe $ n, m $ ser inteiros (para ser definido posteriormente), e $ u, v \ in \ mathbb {r} ^ n $ ser vectores definidos como $$ u [i]=lirt \ {x \ in a \ colon m-x \ equive i \ pmod n \} \ rVer $$ $$ v [i]=lirt \ {y \ in b \ colon m + y \ equiv i \ pmod n \} \ rVer $$ Deixe $ w= u * v $ denotam a convolução circular desses dois vetores. Então se houver $ k $ tal que $$ \ forall x \ em A \ existe y \ em b: y-x= k, $$ então podemos concluir $$ w [K \ bmod n]=sum_ {i: v [i] \ neq 0} v [i] u [i] u [ik \ bmod n]= n $$ qual por construção é o valor máximo que $ W $ pode atingir. Portanto, precisamos só verificar se $ \ max_i w (i)= n $ ou não. Em seguida, verificamos a exatidão da solução, verificando os elementos originais. Computação $ W $ pode ser feito por FFT e FFT inversa na $ \ mathcal {O} (n \ log n) $ tempo e, em seguida, encontrar o elemento máximo e verificá-lo leva $ n $ etapas, então global $ \ mathcal {O} (n \ log n) $ tempo e espaço.

Se os números em ambos os conjuntos forem limitados por $ n $ Esta é uma solução exata. Mas se você escolher $ n $ muito pequeno, $ w (i)= n $ pode acontecer por causa de colisões. Para que possamos verificar todos os elementos para todos os índices que $ w (i) \ GE n $ ; Pode haver vários deles, mas seu número pode ser limitado. Para ter $ \ ell $ tais índices, é preciso ter pelo menos $ 1 + 2 + \ Dots + \ Ell $ Colisões, que implica $$ p [\ lvert \ \ colon w [i] \ ge n \} \ rVer \ ge \ ell] \ le p [\ text {# colisões} \ GE ( \ ell + 1) \ ell / 2]. $$ Existem anelos de elementos de elementos de elementos $ nm de $ a $ e $ B $ . Se escolhermos um número primo $ n $ tal que $ n> 2m $ e escolha $ m $ uniformemente aleatoriamente a partir de $ \ {1, \ DOTS, n \} $ , a probabilidade de colisão é limitada por $ 1 / 2m $ , então pela desigualdade de Markov é $$ \ le \ frac {nm / n} {\ ell ^ 2/2} \ le \ frac {n} {} {\ ell ^ 2} $$ Então, com probabilidade tão perto de $ 1 $ como quiser, $ \ ell=mathcal {O} (\ sqrt} (\ sqrt} (\ sqrt} }) $ . Portanto, a complexidade geral do tempo do algoritmo é $$ \ mathcal {O} (n \ sqrt {n} + m \ log m) $$ Em que $ m \ log m $ é o passo FFT e IFFT (já que definimos $ n= 2m $ ), e $ n \ sqrt {n} $ é a etapa de verificação.

Há duas maneiras pelas quais vejo melhorar isso:

.
1. Pode executar $ \ log n $ Instâncias separadas do algoritmo sem a verificação, e tomar a interseção de índices máximos que $ w [i] \ GE N $ (depois de deslocar por $ m $ ). Se alguém pode mostrar que o número de colisões compartilhadas cai por $ 1/2 $ ou alguma outra constante toda vez, isso mostraria um tempo total de execução de $ \ mathcal {o} (m \ log ^ 2 m) $ .
2. Pode construir um mecanismo de hashing melhor para $ u $ e $ v $ e use momentos mais altos para Markov e tornar a concentração mais nítida.

No entanto, se você está procurando uma solução prática, este algoritmo poderia funcionar muito bem. Por exemplo, os piores

T-Case Comportamento $ \ ell \ APROX \ SQRT {N} $ Ocorre apenas quando os conjuntos são quase progressões aritméticas.Se você escolher elementos quase aleatoriamente, a garantia será muito mais forte.Além disso, você pode parar o passo de verificação assim que encontrar um erro.

Answer 3

Este é um algoritmo completamente diferente, que eu acredito que funciona na $ o (m \ log m) $ pior caso, e deve funcionar para números inteiros ou reais.

Deixe-nos supor que $ a $ a $ e $ B $ já estão em ordem crescente, caso contrário, gastar $ o (n \ log n + m \ log m) $ para classificá-los. Nós fortalecemos um pouco o requisito para algoritmo $ \ mathcal {a} (a, b) $ para retornar todos os índices $ i $ tal que $ a $ a $ pode ser mapeado para $ B $ com offset $ k= b_i-a_1 $ , o que significa que o mapeamento começa na $ b_i $ em diante. A ideia de alto nível é resolver os sub-problemas correspondentes a uma parte inferior da $ a $ e mesclar os índices de uma forma que apenas soluções válidas permaneçam.

A recursão, no entanto, depende de quão próxima $ a $ é uma progressão aritmética. Formalmente, deixe periodicidade $ \ tau (a) $ ser definido como: $$ \ tau (A)=min \ \ \ mathbb {n} ^ +: a_ {i + s + 1} -a_ {i + s}= a_ {i + 1} - a_i \ text {para todos válidos} i, s \} $$ Em palavras, isso significa elementos de $ a $ , são periódicos com um ciclo mínimo $ \ tau (A) $ , até algum offset.

caso eu ( $ \ tau (a) Deixe $ s=tau (a) $ e $ \ ell= a_s - A_1 $ . Recursivamente computar $ i=mathcal {a} (A [1: s], b) $ . Uma observação é que, se $ i, j \ in i $ , correspondendo a conjuntos de índice $ j_i, j_j $ , e $ b_j - B_i=ell $ , o índice define $ j_i, j_j $ pode ser Concatenado para mostrar $ i \ in \ mathcal {a} (A [1: 2S], B) $ . Esta é uma simples conseqüência da $ a $ ser $ S $ periódico, e $ b_j= b_i + \ ell $ garante que o conjunto de índice $ J_J $ inicia onde $ J_i $ termina. Deixar $$ r [i]=lirt \ {j \ in i \ colon j> i, b_j - b_i \ text {divisível por} \ ell} \ rVer $$ Em seguida, $ r [i] $ pode ser calculado com base na $ r [i '] $ que < span class="contêiner de matemática"> $ i '> i $ e o novo conjunto de índice $ i' $ , são os índices que $ r [i] \ GE N / S $ . O custo para este passo é limitado por $ O (m) $ .

case ii ( $ \ tau (a)> n / 3 $ ) : por definição, para $ s= n / 3 $ Deve haver um índice $ i $ que $ a_ {i + 1} -A_i \ neq a_ {i + 1 + s} -a_ {i + s} $ . Se $ i \ le n / 3 $ , teremos $ i, i + s \ le 2n / 3 $ < / span> que certifica que $ \ tau (A [1: 2n / 3])> N / 3 $ . Caso contrário, $ i> n / 3 $ implica que $ \ tau (A [n / 3: n])> n / 3 $ .

Wlog assumir $ \ tau (A [1: 2n / 3)> n / 3 $ e escolha a metade inferior $ A '= A [1: n / 2] $ para recaçar (caso contrário, escolher a metade superior, os mesmos argumentos seguiriam). Recursivamente computar $ i=mathcal {a} (a ', b) $ . Para cada índice $ i \ in i $ , verifique se o restante da sequência pode ser encontrado na $ B $ . Como ambas as seqüências são classificadas, isso pode ser feito em $ o (n) $ passo para cada índice, que implica uma classe geral $ O (| i | \ CDOT n) $ tempo para calcular os índices válidos e devolvê-los como $ \ mathcal {a} (a, b) $ . A eficiência deste passo depende da seguinte reivindicação:

reivindicação: $ | i | \ le 6m / n $ , o que significa que as soluções não são muito sobrepostas.

Prova de reivindicação: Mostramos $ | i |> 6m / n $ leva a uma contradição. Cada índice $ i \ in i $ é o ponto de partida de um conjunto de índices $ j_i= {i= j_1, \ Dots, j_ {n / 2} \} \ subseteq b $ , que map $ a '$ para $ B $ até alguns offset. Col.

Lectivamente, há pelo menos $ 3m $ índices: $$ \ sum_ {i \ in i} | j_i |= | I | n / 2 \ ge 6m / n \ cdot n / 2= 3m $$ Desde a $ |= m $ , por princípio de pombo, há pelo menos um índice $ x \ em b $ / SPAN> aparece em 3 soluções separadas: $$ \ existe x \ em b, r, s, p \ em i \ colon \; x \ in j_r \ cap j_s \ cap j_p $$

Deixe $ S $ Seja a mediana das três $ r . Desde $ x \ in J_S $ e $ | j_s |= n / 2 $ , $ x $ partições $ j_s $ para duas partes, um dos quais deve ter menos de $ N / 4 $ Índices, que assumimos é a parte inferior: $$ J_S= {j_1= s, j_2, \ dots, j_ \ ell= x \}, \ ell \ le n / 4 $$ Por construção, $ s= j_1 $ é mapeado para $ a_1 $ , até $ a_ \ ell $ até alguns offset. Mas também temos $ x \ in J_P $ , isso implica um periódico menor que $ \ ell \ le n / 4 $ em $ a '$ , que contradiz $ \ tau (A')> n / 3 $ . (Há alguns detalhes que vou adicionar mais tarde)

complexidade geral Em cada passo da recursão, pagamos $ O (m) $ . A periodicidade $ \ tau (a) $ também pode ser calculado em $ O (n) $ , por Computando o sufixo mais longo que também é prefixo, de $ \ mathrm {diff} (a) $ , essa é a matriz de incremento $ A_2-A_1, \ DOTS, A_N-A_ {N-1} $ . No entanto, o tamanho do problema reduz pelo menos $ 1/2 $ em cada etapa recursiva. Haverá $ \ log n $ etapas no pior dos casos, o que implica que a complexidade de tempo é limitada por $ O (m \ log n) $ . Adicionando os custos de classificação e, como $ m> n $ , a complexidade geral é limitada pelo tempo de classificação $ O (m \ log m) $