Suponha que eu tenha uma lista de cadeias onde cada cadeia é

exatamente 4 caracteres eexclusivo dentro da lista.

Para cada uma dessas cadeias, quero identificar a posição dos caracteres na cadeia que tornam a cadeia exclusiva.

Então, para uma lista de três strings

abcd
abcc
bbcb

Para a primeira string, quero identificar o caractere na 4ª posiçãod Desde ad não aparece na quarta posição em nenhuma outra string.

Para a segunda string, quero identificar o caractere na 4ª posiçãoc.

Para a terceira corda, eu quero identificar o personagem na 1ª posiçãob E o personagem na 4ª posição, tambémb.

Isso pode ser concisamente representado como

abcd -> ...d
abcc -> ...c
bbcb -> b..b

Se você considerar o mesmo problema, mas com uma lista de números binários

0101
0011
1111

Então o resultado que eu quero seria

0101 -> ..0.
0011 -> .0..
1111 -> 1...

Mantendo o tema binário, posso usar o XOR para identificar quais bits são únicos dentrodois números binários desde

0101 ^ 0011 = 0110

que posso interpretar como significando que, neste caso, o segundo e o terceiro bits (leitura da esquerda para a direita) são únicos entre esses dois números binários. Essa técnica pode ser um arenque vermelho, a menos que, de alguma maneira, possa ser estendida à lista maior.

Uma abordagem de força bruta seria examinar cada sequência por vez e fazer com que cada sequência iterasse pelas fatias verticais do restante das seqüências na lista.

Então, para a lista

abcd
abcc
bbcb

Eu começaria com

abcd

e percorra fatias verticais de

abcc
bbcb

onde essas fatias verticais seriam

a | b | c | c
b | b | c | b

ou em forma de lista, "ab", "bb", "cc", "cb".

Isso resultaria em quatro comparações

a : ab -> . (a is not unique)
b : bb -> . (b is not unique)
c : cc -> . (c is not unique)
d : cb -> d (d is unique)

ou concisamente

abcd -> ...d

Talvez seja uma ilusão, mas tenho a sensação de que deve haver uma solução elegante e geral que se aplique a uma lista arbitrariamente grande de strings (ou números binários). Mas, se houver, ainda não consegui vê-lo.

Espero usar esse algoritmo para derivar assinaturas mínimas de uma coleção de imagens exclusivas (bitmaps) para identificar eficientemente essas imagens em um futuro próximo. Se a eficiência futura não fosse uma preocupação, eu usaria um hash simples de cada imagem.

Você pode melhorar a força bruta?

Editar A abordagem para a qual estou gostando é construir um mapa de pixels para imagens

sprawl[Tuple<x=10, y=33,color=f1fefd>] => {
     image17,
     image23,
     ...
}

sprawl[Tuple<x=10, y=34,color=f1fef0>] => {
     image11
     ...
}

e, em seguida, usando esse mapa para identificar o conjunto mínimo de pixels de assinatura para cada imagem.

Se um pixel (identificado por x, y, cor) fizer referência a apenas uma imagem, eu encontrei uma assinatura (mínima) perfeita para essa imagem.

É mais complicado se uma imagem não tiver pixels únicos, mas como eu sei que todas as imagens são únicas na lista, devo combinar duas ou mais referências de pixel (mas o mínimo possível) para deduzi-la.

Atualizar

Eu tenho trabalhado em um algoritmo para isso. Meu problema é muito parecido comestee escrevi meu algoritmo como umresponda a essa pergunta. Esta atualização deve sinalizar a atenção de quem ainda está seguindo (vejo cinco indicadores). Estou trabalhando nisso isoladamente, para que todo e qualquer feedback seja bem-vindo, mesmo que seja apenas para observar que não me deixei claro!