Sucesores de rango inverso

21

Dado un número entero positivo n, haga lo siguiente (y envíe cada etapa):

  1. comience con una lista que contenga ncopias de n.
  2. hacer los siguientes nhorarios:
  3. en el ipaso th, disminuya gradualmente la ientrada th de la lista hasta que lleguei

Así, por ejemplo, si lo dado nes 4, a continuación, se comienza con [4,4,4,4], y luego en el primer paso que tiene [3,4,4,4], [2,4,4,4], [1,4,4,4]. En el segundo paso, que tiene [1,3,4,4], [1,2,4,4]. En el tercer paso que tienes [1,2,3,4]. Nada se hace en el cuarto paso.

Entonces su salida es [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]].

Se permite cualquier formato de entrada / salida razonable.

Se aplican lagunas estándar . Este es el código de golf : la respuesta con el menor recuento de bytes gana.

Implementación de Python para fines de verificación .

code-golf array-manipulation Monja permeable
fuente
1
Es posible que desee declarar explícitamente que ith siempre está indexado en 1.
Kevin Cruijssen
¿Realmente tenemos que manipular la matriz? Llego a una respuesta más corta sin manipular ninguna matriz, produciendo una salida aceptable.
Olivier Grégoire
2
@ OlivierGrégoire No tiene que seguir los pasos, solo necesita producir la salida en un formato razonable. (es decir, adelante)
Leaky Nun

Respuestas:

6

Jalea , 9 bytes

r€⁸Œp»\QṚ

Pruébalo en línea!

¿Cómo?

r€⁸Œp»\QṚ - Link: integer, N    e.g. 4
 €        - for €ach of implicit range of N (i.e. for i in [1,2,3,...N])
  ⁸       -   with the chain's left argument, N on the right:
r         -     inclusive range (for i<=N this yields [i, i+1, ..., N]
          - ...leaving us with a list of lists like the post-fixes of [1,2,3,....,N]
          -                     e.g. [[1,2,3,4],[2,3,4],[3,4],[4]]
   Œp     - Cartesian product* of these N lists
          -                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,3,4],[1,3,4,4],[1,4,3,4],[1,4,4,4],[2,2,3,4],[2,2,4,4],[2,3,3,4],[2,3,4,4],[2,4,3,4],[2,4,4,4],[3,2,3,4],[3,2,4,4],[3,3,3,4],[3,3,4,4],[3,4,3,4],[3,4,4,4],[4,2,3,4],[4,2,4,4],[4,3,3,4],[4,3,4,4],[4,4,3,4],[4,4,4,4]]
      \   - cumulative reduce with:
     »    -   maximum (vectorises)
          -                     e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,3,4,4],[1,4,4,4],[1,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[2,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[3,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4],[4,4,4,4]]
       Q  - de-duplicate        e.g. [[1,2,3,4],[1,2,4,4],[1,3,4,4],[1,4,4,4],[2,4,4,4],[3,4,4,4],[4,4,4,4]]
        Ṛ - reverse             e.g. [[4,4,4,4],[3,4,4,4],[2,4,4,4],[1,4,4,4],[1,3,4,4],[1,2,4,4],[1,2,3,4]]

* Puede ser más fácil ver lo que está sucediendo con el producto cartesiano utilizado anteriormente con una entrada diferente:

the Cartesian product of [[0,1,2],[3,4],[5]]
is [[0,3,5],[0,4,5],[1,3,5],[1,4,5],[2,3,5],[2,4,5]]
Jonathan Allan
fuente
Superaste a los imposibles de superar.
Leaky Nun
5

R , 83 82 74 bytes

N=rep(n<-scan(),n);while({print(N);any(K<-N>1:n)})N[x]=N[x<-which(K)[1]]-1

Pruébalo en línea!

En lugar de un doble bucle for, un whilebucle es suficiente aquí: encontramos el primer índice donde la lista es mayor que el índice y decrementamos allí.

Ktiene TRUEdonde sea N[i]>i, which(K)devuelve los índices verdaderos, y tomamos el primero con [1].

Giuseppe
fuente
2

JavaScript (ES6), 75 bytes

f=(n,a=Array(n).fill(n))=>[[...a],...a.some(v=>v>++j,j=0)?f(a[j-1]--,a):[]]

Pruébalo en línea!

Arnauld
fuente
2

APL + WIN, 54 bytes

Solicita la entrada de pantalla de entero

((⍴m)⍴n)-+⍀m←0⍪(-0,+\⌽⍳n-1)⊖((+/+/m),n)↑m←⊖(⍳n)∘.>⍳n←⎕

Emite una matriz con cada fila que representa el resultado de cada paso, por ejemplo, para 4:

4 4 4 4
3 4 4 4
2 4 4 4
1 4 4 4
1 3 4 4
1 2 4 4
1 2 3 4
Graham
fuente
2

Jalea , 11 bytes

x`’Jḟḣ1Ʋ¦ÐĿ

Pruébalo en línea!

Cómo funciona

x`’Jḟḣ1Ʋ¦ÐĿ  Main link. Argument: n

x`           Repeat self; yield an array of n copies of n.
         ÐĿ  While the results are unique, repeatedly call the link to the left.
             Return the array of all unique results, including the initial value.
  ’     ¦      Decrement the return value at all indices specified by the chain
               in between.
       Ʋ         Combine the four links to the left into a monadic chain.
   J               Indices; yield [1, ..., n].
    ḟ              Filterfalse; remove all indices that belong to the return value.
     ḣ1            Head 1; truncate the result to length 1.
Dennis
fuente
2

Python 3 , 91 bytes

n=int(input())
x=[n]*n;print(x)
for i in range(n):
    for j in[0]*(n-i-1):x[i]-=1;print(x)

Pruébalo en línea!

Dat
fuente
1 espacio es suficiente para sangrar código en python. Eliminar espacios innecesarios y cambiar a python 2 ahorra 10 bytes: compruébalo
Dead Possum
@DeadPossum, aunque sé que podría hacerlo mejor en Python 2, pronto será obsoleto, así que quería practicar mis habilidades de Python 3 lo más posible.
Dat
2

Java (OpenJDK 8) , 135 bytes

a->{int r[]=new int[a],i=0;java.util.Arrays x=null;x.fill(r,a);for(r[0]++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));}

Pruébalo en línea!

Explicación:

int r[]=new int[a],i=0;    //Initialize array and loop counter
java.util.Arrays x=null;    //reduces the number of of “Arrays” needed from 3 to 1
x.fill(r,a);    //Sets each value in array length n to int n
for(r[0]++;i<a;r[i++]++)    //Increment everything!
  for(;--r[i]>i;    //If decremented array element is larger than element number:
     System.out.print(x.toString(r)));}    //Print the array

Crédito:

-8 bytes gracias a Jonathan Frech !

-16 bytes gracias a Kevin Cruijssen !

-1 byte gracias a Okx !

X1M4L
fuente
44
El import java.util.*;es parte del conteo de bytes, me temo. Y el código de @ JonathanFrech puede jugarse en 4 bytes más colocando el ,i=0después de r[], y cambiando <-~aa <=a. ( Pruébelo en línea. 144 bytes ) (y he cambiado ~-ia i-1para que sea más fácil de leer ..)
Kevin Cruijssen
1
139 bytes eliminando el import java.util.*;mediante el uso de java.util.Arrays x=null;y x.filly x.toString. (Tenga en cuenta que su solución actual es de 155 bytes con la requeridaimport java.util.*;.)
Kevin Cruijssen
1
Golf un byte utilizando en for(;r[i-1]>i;lugar de for(;r[i-1]!=i;.
Okx
2
@KevinCruijssen Podría salvarse otro byte jugando ++i<=aal golf i++<a.
Jonathan Frech
1
Otro byte -2 cambiando la última parte a for(r[0]++;i<a;r[i++]++)for(;--r[i]>i;System.out.print(x.toString(r)));. :) Pruébelo en línea 135 bytes
Kevin Cruijssen
2

Haskell, 69 67 65 63 bytes

Definición recursiva:

f 0=[[]]
f a=map(:(a<$[2..a]))[a,a-1..2]++[1:map(+1)x|x<-f$a-1]

¡Gracias a Laikoni por 2 bytes!

Angs
fuente
El segundo mapes dos bytes más corto con una comprensión de la lista: ¡ Pruébelo en línea!
Laikoni
2

PHP, 153 bytes

Pruébalo en línea!

Código 

function f($n){
$a=array_fill(0,$n,$n);$r=json_encode($a)."\n";$p=0;while($p<$n)
{if($a[$p]!=$p+1){$a[$p]--;$r.=json_encode($a)."\n";}else{$p++;}}echo$r;}

Voy a intentar bajar los bytes o terminar la función recursiva

Explicación

function f($n){
  $a=array_fill(0,$n,$n);          #start with $nlength array filled with $n
  $r=json_encode($a)."\n";         #pushed to the string to output
  $p=0;                            #first position
  while($p<$n){                    #on position $n ($n-1) we do nothing
    if($a[$p]!=$p+1){              #comparing the position+1 to the value
     $a[$p]--;                     #it gets decreased by 1
     $r.= json_encode($a)."\n";    #and pushed
   } else {
     $p++;                       #when position+1 = the value,
   }                               #position is changed ++
  }
   echo $r;
  }
Francisco Hahn
fuente
parece que tiene un espacio en blanco innecesario, por lo que debería ser 153 bytes ; tenga en cuenta que no conozco PHP.
Giuseppe
sí, solo date cuenta, gracias, editando ahora.
Francisco Hahn
1

Python 2 , 80 76 bytes

i=input();l=[i]*i;print l
for x in range(i):
 while l[x]>x+1:l[x]-=1;print l

Pruébalo en línea!

Es un desperdicio tener dos printdeclaraciones, pero no puedo pensar en una mejor manera en este momento.

ElPedro
fuente
75 bytes .
Jonathan Frech
1

Python 2 , 70 bytes

-2 bytes gracias a @LeakyNun
-2 bytes gracias a @JonathanFrech

i=I=input()
l=[I]*I
exec"exec'print l;l[-i]-=1;'*max(~-i,2);i-=1;"*~-I

Pruébalo en línea!

Zarigüeya muerta
fuente
1
(I-1)->~-I
Leaky Nun
1
70 bytes , inicializando i=Iy decrementando.
Jonathan Frech
1

J , 17 15 bytes

+/\@,(#=)@i.&.-

Pruébalo en línea!

Explicación

+/\@,(#=)@i.&.-  Input: n
              -  Negate n
          i.     Reverse of range [0, n)
       =           Identity matrix of order n
      #            Copy each row by the reverse range
              -  Negate
    ,            Prepend n
+/\              Cumulative sum of rows
millas
fuente
1

Retina , 49 bytes

.+
*
_
$`_,$= 
.{*\`_+,(_+)
$.1
0`(\b(_+),\2)_
$1

Pruébalo en línea! Explicación:

.+
*

Convierta la entrada a unario.

_
$`_,$=

Cree una lista de n copias de i,ndónde iestá el índice de la copia.

.

No imprima nada (cuando finalice el bucle).

{

Haga un bucle hasta que el patrón no cambie.

*\`_+,(_+)
$.1

Borre temporalmente el isy convierta eln s en decimal y en salida.

0`(\b(_+),\2)_
$1

Tome la primera entrada de la lista cuyo valor excede su índice y decremente.

Neil
fuente
1

Python 3 , 70 67 65 bytes

def f(n):
 k=0;a=[n]*n
 while k<n-1:print(a);k+=a[k]==k+1;a[k]-=1

Pruébalo en línea!

  • (67) Convertir a función: -3 bytes
  • (65) Eliminar paréntesis innecesarios: -2 bytes

Versión sin golf:

def f(n):
    k = 0
    a = [n] * n             # create n-item list with all n's
    while k < n - 1:        # iterate through columns 0..n-1
        print(a)            # print whole list
        if a[k] == k + 1:   # move to the next column when current item reaches k+1
            k += 1
        a[k] -= 1           # decrement current item
xbarbie
fuente
0

C (clang) , 131 141 bytes

i,j,k,m[99];p(){for(k=0;m[k];printf("%d ",m[k++]));puts("");}f(n){for(j=k=m[n]=0;k<n;m[k++]=n);p();for(;j<n;j++)for(i=1;i++<n-j;m[j]--,p());}

Pruébalo en línea!

Esto funcionará para todos nhasta 99. TIO trunca la salida. Puede admitir arbitrariamente más grande ncambiando el tamaño de la matrizm según lo permita la memoria.

El seguimiento está limitado a n = 1..9 pero es significativamente más corto

C (clang) , 89 92 bytes

i,j;char m[12];f(n){j=!puts(memset(m,n+48,n));for(;j<n;j++)for(i=1;i++<n-j;m[j]--,puts(m));}

Pruébalo en línea!

Actualizado: modificado para evitar la dependencia de la inicialización estática

GPS
fuente
Tu static/global initialization because multiple test casesno está permitido, ya que las funciones tienen que ser invocables más de una vez.
Jonathan Frech
@ Jonathan Respuestas actualizadas. Siempre me pregunté si esto debería permitirse, y no podía decidirme.
GPS
1
Aquí está la meta publicación relevante: codegolf.meta.stackexchange.com/a/4940/73111
Jonathan Frech
Usted podría campo m[j]--,p()a p(m[j]--)y guardar un byte.
Jonathan Frech
128 bytes
ceilingcat
0

Clojure, 132 bytes

#(loop[R[(vec(repeat % %))]j(- % 2)i 0](if(> i j)R(recur(conj R(update(last R)i dec))(if(= i j)(- % 2)(dec j))(if(= i j)(inc i)i))))

Esperaba que esto fuera más corto ...

Menos con estado pero más largo en 141 bytes:

#(apply map list(for[i(range %)](concat(repeat(nth(cons 0(reductions +(reverse(range %))))i)%)(range % i -1)(if(>(dec %)i)(repeat(inc i))))))
NikoNyrh
fuente
0

Python 3, 101 bytes

def f(n):
 p=print;m=[n for_ in range(n)];p(m)
 for i in range(n):
    while m[i]>1+i:m[i]-=1;p(m)

Probablemente podría jugar más golf con la impresión, pero estoy lejos de mi computadora y no estoy completamente seguro de las reglas de Python 2 para configurar una variable para imprimir. Actualizaré más tarde cuando llegue a una computadora o si alguien aclara en los comentarios.

sonrad10
fuente