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!)^2
fórmulas, cada una con 2k-1
variables y k^2
té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, 1010
no 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 .
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?Respuestas:
Mathematica, O (k ^ 2 (k!) ^ 2) tiempo
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:
&
al final lo convierte en una función pura, con#
referencia al primer argumento, que#2
es 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 paraUnion
, 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#n
refiere a sus argumentos más internos.Fold[*..*&,#,*..*]
toma una función de acumulador, un valor inicial y una lista, y devuelvef[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 anteriorFlatten
.StringReplace[#,#2->"0/1"]
toma el resultado anterior y lo devuelve con la variable actual reemplazada por cualquiera0
o1
.fuente
k
como variable en tu tiempo? Aún así, el tiempo factorial! ¡Uf!k
". Además, tuve que hacer unGeneralUtilities`Benchmark
para cada método utilizado.