Códigos grises generalizados

13

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.

Anush
fuente
1
(¿debería "sumar o restar 1" módulo realizado I_i+1? ¿Puede alcanzar 0 desde I_i?)
usuario202729
@ user202720 No, no tenía la intención de eso.
Anush
¿Cómo funciona la complejidad cuando ny kson limitados? suponiendo que van al infinito con ancho de bits cómo ir
l4m2
@ l4m2 Para el análisis de complejidad, suponga que k va al infinito.
Anush
@Anush, ¿cómo va el ancho de bits?
l4m2

Respuestas:

4

Python 3 , 116 bytes

def f(a):
 l=len(a);t=[0]*l;d=[1]*l
 while 1:
  i=0;yield t
  while not-1<t[i]+d[i]<=a[i]:d[i]*=-1;i+=1
  t[i]+=d[i]

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, es print(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.

usuario202729
fuente
¿Cuánto tiempo dura el ciclo while interno?
Anush
@Anush En la mayoría de los kpasos, porque en cada paso iaumenta en 1y después de los kpasos i==ky d[i]causa un error.
user202729
Esta es una muy buena solución.
Anush
Puede guardar un byte reemplazándolo not 0<=con not-1<.
1
¿Podrías usar en yield tlugar de print(t,flush=1)?
Dennis
2

Stax , 22 bytes

▒)∙ñ╚▀NK♀F☺S(A#P`░]╪Db

Ejecutar y depurarlo

Aquí hay uno grande para mostrar el comportamiento asintótico Presione ejecutar.

Desempaquetado, sin golf y comentado, se ve así.

,           pop from input to main stack
W           run the rest of the program repeatedly until explicitly cancelled
  cJP       copy top of stack and print, delimited by spaces
            get the index to mutate
  i^            iteration index + 1
  x{^|%}I       repeatedly apply divmod using l[k]+1 from input
                get the index of the first value that returns modulus >0
  cU=C      if the result is -1 (no match), then terminate the program
            get the direction to mutate
  s             get the "div" part of the last div operation called "d"
  ^|1           -1 ^ (d+1)
  ~{+}&     increment element in array at the index by the calculated amount

Ejecute este

recursivo
fuente
1
Con unas medidas de complejidad bits, índice de iteración es O(k)bits, por lo división de ktiempos pueden tomar O(k²)el tiempo ...
user202729
1

JavaScript (Node.js) , 114 bytes

a=>{b=a.map(_=>0);c=a.map(_=>1);for(i=0;a[i];b[i]+=c[i]||-1){console.log(b);for(i=0;b[i]==a[i]*c[i];i++)c[i]^=1;}}

Pruébalo en línea! Sin golf:

function ggray(maxima) {
    var current = Array(maxima.length).fill(0);
    var flag = Array(maxima.length).fill(1);
    for (;;) {
        console.log(current);
        for (var i = 0; ; i++) {
            if (i == maxima.length) return;
            if (current[i] != maxima[i] * flag[i]) break;
            flag[i] = 1 - flag[i];
        }
        if (flag[i]) current[i]++;
        else current[i]--;
    }
}
Neil
fuente
1

Kotlin , 181 178 bytes

Gracias a: Anush señaló que entendí mal el desafío de guardar 2 bytes. Ovs señaló un ahorro de 1 byte.

val p={a:List<Int>->var l=a.size
val v=Array(l,{0})
val i=Array(l,{1})
l-=1
o@while(0<1){println(v)
var p=l
while(v[p]+i[p]!in 0..a[p]){i[p]*=-1
p-=1
if(p<0)break@o}
v[p]+=i[p]}}

Pruébalo en línea!

JohnWells
fuente
1
Para el ejemplo en la pregunta con 2 1 3, su código necesita 3 2 4 como entrada parece.
Anush
1
while(true)puede serwhile(1<2)
ovs