¿Cuál es la forma más eficiente de generar el conjunto $S$ de cadenas binarias únicas de una longitud determinada, $L$ ¿si todas las cadenas son únicas bajo la operación de inversión? Por ejemplo, si $L = 2$ los elementos de $S$ sería {00, 01, 11}. Además, ¿qué es $||S||$ en función de $L$ ?
Respuestas
¿Demasiados anuncios?
Generar todas las cadenas de longitud $L$ y descartar los que sean lexicográficamente mayores que su inverso.
El número de cadenas que produce es $2^L$ menos la mitad del número de cadenas que son no palíndromos. Existen $2^{\lceil L/2 \rceil}$ palíndromos, por lo que $$|S| = 2^L - \frac{2^L - 2^{\lceil L/2\rceil}}{2} = 2^{L-1} + 2^{\lceil L/2\rceil-1}$$
delroh
Puntos
56
Para cada cadena $x$ ,
- Si $x$ es un palíndromo ( $x = x^R$ ), elígelo.
- En caso contrario, elija $x$ o $x^{R}$ pero no ambos.
El tamaño máximo de $S$ es $$ \frac{2^L - P}{2} + P = \frac{2^L+P}{2}, $$ donde $P$ es el número de palíndromos de longitud $L$ . ¿Puedes ver por qué $P$ es igual a $$ 2^{\lceil \frac{L}{2} \rceil}? $$
