La distancia de Hamming entre dos cadenas de igual longitud es el número de posiciones en las que los símbolos correspondientes son diferentes.
Dejado P
ser una cadena binaria de longitud n
y T
ser una cadena binaria de longitud 2n-1
. Podemos calcular las n
distancias de Hamming entre P
y cada n
subcadena de longitud T
en orden de izquierda a derecha y ponerlas en una matriz (o lista).
Ejemplo de secuencia de distancia de Hamming
Deje P = 101
y T = 01100
. La secuencia de distancias de Hamming que obtienes de este par es 2,2,1
.
Definición de cercanía
Ahora consideremos dos secuencias de distancias de Hamming. Decir x = (0, 2, 2, 3, 0)
y y = (2, 1, 4, 4, 2)
como ejemplos. Decimos eso x
y y
somos close
si y <= x <= 2*y
o si x <= y <= 2*x
. Aquí la multiplicación escalar y la desigualdad se toman de manera elemento. Es decir, para dos secuencias A
y B
, A <= B iff A[i] <= B[i]
para todos los índices i
.
Tenga en cuenta que las secuencias de distancias de Hamming forman un orden parcial en esta forma de compararlas. En otras palabras, muchos pares de secuencias no son ni mayores ni iguales ni menores ni iguales entre sí. Por ejemplo (1,2)
y (2,1)
.
Entonces, usando el ejemplo anterior, (0, 2, 2, 3, 0) <= 2*(2, 1, 4, 4, 2) = (4, 2, 8, 8, 4)
pero (0, 2, 2, 3, 0)
no es más grande que (2, 1, 4, 4, 2)
. Tampoco (2, 1, 4, 4, 2)
es menor o igual que 2*(0, 2, 2, 3, 0) = (0, 4, 4, 6, 0)
. Como resultado x
y y
no están cerca el uno del otro.
Tarea
Para aumentar a n
partir de n=1
, considere todos los pares posibles de cadenas binarias P
de longitud n
y T
longitud 2n-1
. Hay 2^(n+2n-1)
tales pares y, por lo tanto, muchas secuencias de distancias de Hamming. Sin embargo, muchas de esas secuencias serán idénticas. La tarea es encontrar el tamaño del conjunto más grande de secuencias de distancia de Hamming para que no haya dos secuencias cercanas entre sí.
Su código debe generar un número por valor de n
.
Puntuación
En general, su puntaje es el más alto n
que alcanza su código en mi máquina en 5 minutos (pero siga leyendo). El tiempo es para el tiempo total de funcionamiento, no el tiempo solo para eso n
.
Para dar puntajes a las respuestas no óptimas, ya que es probable que sea difícil encontrar respuestas óptimas, necesitaremos un sistema de puntuación ligeramente sutil. Su puntaje es el valor más alto n
para el cual nadie más ha publicado una respuesta correcta más alta para cualquier tamaño que sea menor que igual a esto. Por ejemplo, si usted emite 2, 4, 21
y alguien más emite, 2, 5, 15
entonces solo puntuaría 1
como alguien más tiene una mejor respuesta para n = 2
. Si genera 2, 5, 21
resultados, obtendría puntajes 3
sin importar los resultados de cualquier otra persona, porque esas respuestas son todas óptimas. Claramente, si tiene todas las respuestas óptimas, obtendrá la puntuación más alta n
que publique. Sin embargo, incluso si su respuesta no es la óptima, aún puede obtener el puntaje si nadie más puede superarlo.
Ejemplo de respuestas y ejemplo trabajado
(Estas respuestas aún no están marcadas. Se recibiría agradecidamente la verificación independiente).
Gracias a ETHproductions:
- n = 1 da 2.
- n = 2 da 5.
- n = 3 da 21.
Veamos n = 2
con más detalle. En este caso, la lista completa de secuencias de distancia de Hamming (representada por tuplas aquí) es:
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]
Podemos ver que (0,0)
no está cerca de ninguna otra tupla. De hecho, si tomamos (0, 0)
, (0, 1)
, (1, 0)
, (2, 1)
, (1,2)
entonces ninguna de esas tuplas están cerca de cualquiera de los otros. Esto da una puntuación de 5
para n = 2
.
Para n = 3
la lista completa de distintas secuencias de distancia de Hamming es:
[(0, 0, 0), (0, 0, 1), (0, 1, 1), (0, 1, 2), (0, 1, 3), (0, 2, 1), (0, 2, 2), (0, 2, 3), (0, 3, 0), (0, 3, 1), (1, 0, 0), (1, 0, 1), (1, 0, 2), (1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 0), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 0), (1, 3, 1), (1, 3, 2), (2, 0, 1), (2, 0, 2), (2, 0, 3), (2, 1, 0), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 0), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 0, 2), (3, 0, 3), (3, 1, 0), (3, 1, 1), (3, 1, 2), (3, 2, 0), (3, 2, 1), (3, 2, 2), (3, 3, 2), (3, 3, 3)]
De esas 48
secuencias, podemos elegir un conjunto de tamaños 21
para que ningún par en ese conjunto esté cerca el uno del otro.
Idiomas y bibliotecas
Puede usar cualquier idioma y bibliotecas disponibles que desee. Siempre que sea posible, sería bueno poder ejecutar su código, por lo tanto, si es posible, incluya una explicación completa sobre cómo ejecutar / compilar su código en Linux.
Mi máquina Los tiempos se ejecutarán en mi máquina de 64 bits. Esta es una instalación estándar de ubuntu con 8 GB de RAM, procesador AMD FX-8350 de ocho núcleos y Radeon HD 4250. Esto también significa que necesito poder ejecutar su código.
Respuesta líder
- Puntuación de 4 por 2, 5, 21, 83, 361 por Christian Sievers. C ++
- Puntuación de 5 para 2, 5, 21, 83, 372 por fəˈnɛtɪk. Javascript
Respuestas:
C ++ usando la biblioteca igraph
¡Gracias por una buena oportunidad para aprender una nueva biblioteca!
Este programa ahora calcula
2, 5, 21, 83, 361
rápido. Puede controlar la impresión de los nodos con laPRINTNODES
constante.El gráfico utilizado tiene bordes adicionales entre los nodos correspondientes a los vectores de distancia donde uno está cerca (pero no es igual) al otro invertido. Eso acelera el cálculo, y cualquier conjunto independiente encontrado es, por supuesto, también uno de los gráficos originales. Además, incluso si no se aplica por completo, el conjunto independiente calculado se cierra bajo reversión. Creo que siempre existe un conjunto independiente máximo con esa propiedad. Al menos hay uno para
n<=4
. (Estoy seguro de que puedo mostrar que 83 es óptimo).Para compilar en Debian, instalar
libigraph0-dev
y hacerg++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o ig ig.cpp -ligraph
.Descripción anterior:
La biblioteca igraph tiene una función para calcular el tamaño máximo de un conjunto de vértices independiente de un gráfico. Puede manejar este problema hasta
n=3
en menos de un segundo y no termina en díasn=4
.Entonces, lo que hago es descomponer el gráfico en componentes conectados y dejar que la biblioteca maneje los
MAXDIRECT
componentes pequeños (menos que los nodos). Para los otros componentes, selecciono un vértice y lo elimino. En el mejor de los casos, esto divide el gráfico en varios componentes, pero generalmente no lo hace. De todos modos, los componentes (tal vez solo uno) son más pequeños y podemos usar la recursividad.Obviamente, la selección del vértice es importante. Solo tomo uno de grado máximo. Descubrí que obtengo mejores resultados (pero solo para
n=4
) cuando uso una lista de nodos invertida. Eso explica la parte mágica de laconstruct
función.Puede valer la pena mejorar la selección. Pero parece más importante reconsiderar los nodos eliminados. En este momento, nunca los vuelvo a mirar. Algunos de ellos pueden estar desconectados de cualquiera de los nodos seleccionados. El problema es que no sé qué nodos forman el conjunto independiente. Por un lado, la eliminación de nodos renumera los nodos restantes. Eso puede manejarse adjuntando atributos a ellos. Pero peor, el cálculo del número de independencia solo da este número. La mejor alternativa que ofrece la biblioteca es calcular todos los conjuntos independientes más grandes, que es más lento (cuánto parece depender del tamaño del gráfico). Aún así, este parece ser el camino inmediato a seguir. Mucho más vagamente, también creo que podría ser útil considerar si podemos usar la forma especial en que se define el gráfico.
El caso
n=6
podría ser accesible (en absoluto, no necesariamente en 5 minutos) si reemplazo la recursión con un bucle usando una cola para los componentes restantes.Me pareció interesante mirar los componentes de los gráficos. Para
n=4
, sus tamaños son168, 2*29, 2*28, 3, 4*2, 4*1
. Solo el más grande no se puede manejar directamente.Para
n=5
, los tamaños son1376, 2*128, 2*120, 119, several <=6
.Espero que esos tamaños dobles correspondan a gráficos isomórficos, pero usar esto no parece valioso porque siempre hay un único componente dominante:
Para
n=6
, el componente más grande contiene11941
nodos (de un total de15425
), los siguientes dos componentes más grandes tienen tamaño596
.Para
n=7
, estos números son107593 (125232), 2647
.fuente
g++ -std=c++11 -Wall -O3 -I/usr/include/igraph -o sievers sievers.cpp -ligraph
. Importa dónde-ligraph
está.set
que uso para evitar duplicados, pero ni siquiera pensé en su orden cuando escribí ese código. El bucle interno que comienza eni+1
solo evita mirar un par y también su versión intercambiada, que no es necesaria, y es la forma más fácil de evitar bucles (bordes(a,a)
). No depende del orden en que vienen los nodos, no me importa si consigo(a,b)
o(b,a)
.Javascript, Seq: 2,5,21,
8183,37267,349Logré aumentar el valor para 4 usando la eliminación aleatoria de elementos al comienzo de mi búsqueda. Por extraño que parezca, eliminar 20 elementos con más de 6 conexiones fue más rápido que eliminar 5 elementos con más de 8 conexiones ...
Sin embargo, esta secuencia probablemente no sea óptima para 5 y podría no ser óptima para 4. Sin embargo, ninguno de los nodos está cerca de otro en el conjunto.
Código:
Pruébalo en línea!
Fragmento que se puede agregar al final del programa para mostrar qué secuencias de distancia de Hamming seleccionan cada secuencia de distancia de Hamming
Explicación:
Primero, el código genera todas las distancias de hamming únicas desde las subcadenas.
Luego, el código convierte esta lista en un gráfico no dirigido
Finalmente, el código recorre este gráfico, eliminando el vértice con la mayor cantidad de conexiones en cada ciclo antes de restaurar cualquier nodo que ahora tenga menos conexiones que el máximo actual. Cuando ha terminado con este ciclo, genera el número de nodos restantes
Conjuntos
1:
2:
3:
4:
5:
fuente