Supongamos que tengo una lista de cadenas donde cada cadena es

exactamente 4 caracteres de largo yÚnico dentro de la lista.

Para cada una de estas cadenas, quiero identificar la posición de los caracteres dentro de la cadena que hacen que la cadena sea única.

Entonces, para una lista de tres cadenas

abcd
abcc
bbcb

Para la primera cadena quiero identificar el personaje en cuarta posiciónd ya qued no aparece en la cuarta posición en ninguna otra cadena.

Para la segunda cadena quiero identificar el personaje en la 4ta posiciónc.

Para la tercera cadena, quiero identificar el personaje en la primera posiciónb Y el personaje en cuarta posición, tambiénb.

Esto podría representarse concisamente como

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

Si considera el mismo problema pero con una lista de números binarios

0101
0011
1111

Entonces el resultado que quiero sería

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

Manteniéndome con el tema binario, puedo usar XOR para identificar qué bits son únicos dentro dedos números binarios desde

0101 ^ 0011 = 0110

lo que puedo interpretar en el sentido de que en este caso los bits segundo y tercero (lectura de izquierda a derecha) son únicos entre estos dos números binarios. Esta técnica puede ser un arenque rojo a menos que de alguna manera se pueda extender a la lista más grande.

Un enfoque de fuerza bruta sería mirar cada cadena por turno y que cada cadena iterara a través de cortes verticales del resto de las cadenas en la lista.

Entonces para la lista

abcd
abcc
bbcb

Yo comenzaría con

abcd

e iterar a través de rebanadas verticales de

abcc
bbcb

donde estas rebanadas verticales estarían

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

o en forma de lista, "ab", "bb", "cc", "cb".

Esto resultaría en cuatro comparaciones

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

o concisamente

abcd -> ...d

Tal vez sea una ilusión, pero tengo la sensación de que debería haber una solución elegante y general que se aplicaría a una lista arbitrariamente grande de cadenas (o números binarios). Pero si existe aún no he podido verlo.

Espero usar este algoritmo para obtener firmas mínimas de una colección de imágenes únicas (mapas de bits) para identificar de manera eficiente esas imágenes en el futuro. Si la eficiencia futura no fuera una preocupación, usaría un hash simple de cada imagen.

¿Se puede mejorar la fuerza bruta?

Editar El enfoque al que me estoy calentando es construir un mapa de píxeles a imágenes

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

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

y luego usar ese mapa para identificar el conjunto mínimo de píxeles de firma para cada imagen.

Si un píxel (identificado por x, y, color) hace referencia a una sola imagen, entonces he encontrado una firma perfecta (mínima) para esa imagen.

Es más complicado si una imagen no tiene píxeles únicos, pero como sé que todas las imágenes son únicas dentro de la lista, debería poder combinar dos o más referencias de píxeles (pero la menor cantidad posible) para deducir la imagen.

Actualizar

He estado trabajando en un algoritmo para esto. Mi problema es muy similar aéste, y he escrito mi algoritmo comoresponde a esa pregunta. Esta actualización es para llamar la atención de cualquiera que siga (veo cinco marcadores). Estoy trabajando en esto de forma aislada, por lo que todos los comentarios son bienvenidos, ¡aunque solo sea para observar que no me he aclarado!