Entrada: Una matriz I de k enteros positivos. Los enteros no serán mayores que 100 y k ≤ 100 .
Salida: Su código debe generar todas las matrices posibles O de enteros no negativos de longitud k con la restricción de que 0 ≤ O i ≤ I i . Para pasar de una matriz a la siguiente, puede sumar o restar 1 a un valor en la matriz. Su código no debe generar la misma matriz dos veces. Si el número de matrices diferentes que se emitirán es muy grande, su código debería continuar emitiéndose para siempre hasta que se elimine.
Ejemplos
Si I es una matriz de k unos, entonces este es exactamente el problema de iterar sobre todos los códigos Gray de ancho de bits k , excepto que el primer y el último elemento no necesitan ser accesibles en un solo paso.
Si
I = [2,1]
entonces una posible ordenación de las matrices de salida es(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
- Si es
I = [2,1,3]
así, una posible ordenación de las matrices de salida es(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),...
.
Este es un desafío de código de golf, la presentación con el código fuente con la menor longitud gana. No permita que las respuestas cortas en idiomas de golf lo desalienten a publicar una respuesta en otros idiomas. Intenta encontrar la respuesta más corta en cualquier idioma.
Este también es un desafío de complejidad restringida. Cada nueva matriz debe emitirse con un tiempo O (k) transcurrido desde la matriz anterior (o el inicio del programa para la primera matriz emitida). Esto significa que el tiempo de ejecución por nueva matriz de salida (cada uno tiene una longitud k ) no debe ser mayor que O (k) . Es decir, debe tomar un tiempo proporcional a k y no, por ejemplo, k 2 o 2 k . Tenga en cuenta que este no es el tiempo promedio por salida, sino el peor de los casos para todos y cada uno de los arreglos generados.
Puede suponer que toda la aritmética en enteros de 64 bits se puede realizar en tiempo constante, al igual que leerlos y generarlos, así como asignarlos, buscarlos y cambiar valores en matrices.
Una consecuencia de la complejidad restringida es que las soluciones que solo salen al salir del programa no son aceptables.
I_i+1
? ¿Puede alcanzar 0 desdeI_i
?)n
yk
son limitados? suponiendo que van al infinito con ancho de bits cómo irRespuestas:
Python 3 , 116 bytes
Pruébalo en línea!
Gracias nemotécnico por -1 byte.
Función generadora. (gracias Dennis por recordarme, olvidé que existe la función) Si la salida debe imprimirse en stdout, usar
print(t,flush=1)
9 bytes adicionales, o si se llama a Python con-u
, esprint(t)
suficiente para +1 bytes.Se detiene con un error (
IndexError
). Si desea llamar a esta función y luego continuar el programa, debe atraparlo.fuente
k
pasos, porque en cada pasoi
aumenta en1
y después de losk
pasosi==k
yd[i]
causa un error.not 0<=
connot-1<
.yield t
lugar deprint(t,flush=1)
?Stax , 22 bytes
Ejecutar y depurarlo
Aquí hay uno grande para mostrar el comportamiento asintótico Presione ejecutar.
Desempaquetado, sin golf y comentado, se ve así.
Ejecute este
fuente
O(k)
bits, por lo división dek
tiempos pueden tomarO(k²)
el tiempo ...JavaScript (Node.js) , 114 bytes
Pruébalo en línea! Sin golf:
fuente
Kotlin ,
181178 bytesGracias a: Anush señaló que entendí mal el desafío de guardar 2 bytes. Ovs señaló un ahorro de 1 byte.
Pruébalo en línea!
fuente
while(true)
puede serwhile(1<2)