Número de salidas únicas sustituyendo variables

9

Dado un conjunto de fórmulas como esta:

bacb
bcab
cbba
abbc

Proporcione un algoritmo que encuentre el número de resultados únicos que puede obtener cuando cada variable se sustituye por "0" o "1" en cada fórmula.

Hay (k!)^2fórmulas, cada una con 2k-1variables y k^2términos. Exprese sus asintóticas en términos de k.

El algoritmo más rápido gana. En caso de empate, la solución con menor uso de memoria asintótica gana. Si eso sigue siendo un empate, el primer puesto gana.


Para el ejemplo anterior, se pueden obtener los siguientes resultados sustituyendo las variables:

1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

Entonces la respuesta correcta es 12. Entre otras, 1010no se puede hacer usando las fórmulas anteriores.

He hecho tres pruebas más casos, con las soluciones respectivas de 230 , 12.076 y 1.446.672 .

orlp
fuente
Aclaración: ¿qué es k en la pregunta? ¿Es solo una constante abstracta?
isaacg
@isaacg Sí. Es para evitar vínculos entre soluciones que son más rápidas para fórmulas menos grandes pero más grandes, por ejemplo.
orlp
Entonces, cada letra a, b... ¿es una variable ? ¿Y siempre tenemos solo un número desigual de variables? ¿No importa cuánto dura la secuencia de variables y cuántas fórmulas se le dan?
flawr
@flawr La relación exacta entre el número de variables, el número de términos y el número de fórmulas se da en la pregunta.
orlp
¿'Puede ser' significa que puede obtener hasta $ (k!) ^ 2 $ fórmulas o hay exactamente $ (k!) ^ 2 $ fórmulas? Además de eso, ¿tiene alguna aplicación para un algoritmo con esas especificaciones? Solo pregunto porque las especificaciones parecen ser bastante arbitrarias.
flawr

Respuestas:

2

Mathematica, O (k ^ 2 (k!) ^ 2) tiempo

Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Con suerte calculé la complejidad del tiempo correctamente. La entrada es una lista de fórmulas como {"bacb","bcab","cbba","abbc"}. Se ejecuta en menos de 30 segundos para cada caso de prueba en mi máquina, pero ¿a quién le importan los tiempos absolutos?

Explicación:

  • En primer lugar, &al final lo convierte en una función pura, con #referencia al primer argumento, que #2es el segundo argumento, etc.
  • Length[*..*] toma la longitud de la lista contenida dentro de ella.
  • Union@@(*..*)toma la lista contenida y la proporciona como argumentos para Union, lo que devuelve una lista de los elementos únicos en cualquiera de sus argumentos.
  • *..*&/@#toma una función pura y la asigna sobre la lista de fórmulas, para que se {a,b,c}convierta {f[a],f[b],f[c]}. Tenga en cuenta que en funciones puras anidadas, se #nrefiere a sus argumentos más internos.
  • Fold[*..*&,#,*..*]toma una función de acumulador, un valor inicial y una lista, y devuelve f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] toma todos los caracteres en la fórmula actual y obtiene todos los elementos únicos, dándonos las variables.
  • Flatten[*..*]aplana su argumento, para que se {{{a},b},{{c,{d}}}}convierta {a,b,c,d}.
  • {*..*,*..*}es simplemente una forma de combinar los dos resultados usando lo anterior Flatten.
  • StringReplace[#,#2->"0/1"]toma el resultado anterior y lo devuelve con la variable actual reemplazada por cualquiera 0o 1.
LegionMammal978
fuente
¿Por qué estás usando kcomo variable en tu tiempo? Aún así, el tiempo factorial! ¡Uf!
theonlygusti
El operador dijo: "Exprese sus asintóticos en términos de k". Además, tuve que hacer un GeneralUtilities`Benchmarkpara cada método utilizado.
LegionMammal978
¿Le gustaría agregar una descripción sencilla en inglés de su algoritmo? No estoy familiarizado con Mathematica, por lo que no puedo verificar su solución.
orlp