Ordenar filas y columnas en una matriz 2D

15

Dada una matriz 2D de enteros, clasifiquemos sus filas y columnas en bloques. Esto significa que solo tiene que ordenar una fila o columna dada, pero aplicando las transformaciones necesarias para ordenarla a cada otra fila o columna en la matriz 2D.

Reglas

  • La entrada será una matriz 2D de enteros y un entero indexado 1. Este entero representará la fila que se ordenará si el número es positivo, o la columna que se ordenará si el número es negativo (o al revés que desee). Ejemplo: Dada una 4x3matriz (filas x columnas), puede ordenar la segunda columna con un -2argumento o la tercera fila con un 3argumento. Este segundo argumento nunca será cero y su valor absoluto nunca será mayor que la dimensión correspondiente de la matriz.
  • La salida también será una matriz 2D de enteros con las transformaciones necesarias aplicadas para ordenar la fila o columna dada. Alternativamente, puede escribir la matriz en STDOUT.
  • La matriz de salida tendrá la fila o columna especificada ordenada en orden ascendente. Solo tenga en cuenta que cuando necesite intercambiar dos números seguidos, se intercambiarán todas las columnas donde se encuentran los números. Y cuando necesite intercambiar dos números en una columna, se intercambiarán todas las filas donde se encuentran los números.
  • En el caso en que el mismo número aparezca varias veces en la fila / columna que se va a ordenar, habrá varias soluciones posibles de acuerdo con la forma en que intercambia los valores, solo haga lo que corresponda con el resto de filas / columnas que se intercambiarán.

Ejemplos

Positive indices for rows and negative indices for columns

[5  8  7  6                                  [1  3  2  4
 1  3  2  4   order by -3 (3rd column)  -->   9  6  3  0
 9  6  3  0]                                  5  8  7  6]

[5  8  7  6                                  [9  6  3  0
 1  3  2  4   order by -4 (4th column)  -->   1  3  2  4
 9  6  3  0]                                  5  8  7  6]

[5  8  7  6                                  [5  7  8  6
 1  3  2  4     order by 2 (2nd row)  -->     1  2  3  4
 9  6  3  0]                                  9  3  6  0]

[5  8  7  6                                  [6  7  8  5
 1  3  2  4     order by 3 (3rd row)  -->     4  2  3  1
 9  6  3  0]                                  0  3  6  9]

[1  2                                    [1  2     [3  2
 3  2]   order by -2 (2nd column)  -->    3  2] or  1  2]  (both are valid)

[7  5  9  7                                  [5  7  7  9     [5  7  7  9
 1  3  2  4     order by 1 (1st row)  -->     3  1  4  2  or  3  4  1  2
 9  6  3  0]                                  6  9  0  3]     6  0  9  3]

Este es el , ¡así que puede ganar el código más corto para cada idioma!

Charlie
fuente
Esto viene de la caja de arena .
Charlie
¿Podemos cambiar la representación entera? negativo para filas y positivo para columnas?
Luis felipe De jesus Munoz
1
@LuisfelipeDejesusMunoz sí, eso se afirma en la pregunta.
Charlie
¿Puede una fila / columna contener números duplicados?
Kevin Cruijssen
@KevinCruijssen sí, vea los últimos ejemplos y el último punto de las reglas.
Charlie

Respuestas:

5

Matlab, 73 62 47 bytes

@(m,i){sortrows(m,-i) sortrows(m',i)'}{(i>0)+1}

Pruébalo en línea!

-11 bytes gracias a @Giuseppe.

-15 bytes gracias a @LuisMendo.

DimChtz
fuente
4

Japt , 18 17 bytes

negativo para filas y positivo para columnas

>0?VñgUÉ:ßUa Vy)y

Pruébalo en línea!

Luis felipe De jesus Munoz
fuente
Esto falla cuando Ues negativo; sin embargo, la versión anterior de 17 bytes funciona.
Shaggy
@ Shaggy Mi mal, pensé que funcionaría de todos modos, no lo comprobé en absoluto
Luis felipe De jesus Munoz el
Sin embargo, no es una mala idea pasar una función como el primer argumento al ßque se aplica automáticamente U. Podría crear problemas al tratar de pasar cadenas literales, pero publicar una sugerencia al repositorio de GitHub de todos modos para una mayor investigación.
Shaggy
4

05AB1E , 25 24 14 bytes

diø}Σ¹Ä<è}¹diø

Enorme -10 bytes gracias a @Emigna .

Utiliza una entrada entera positiva para ordenar las filas, negativa para las columnas.

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

di }      # If the (implicit) integer input is positive:
  ø       #  Swap the rows and columns of the (implicit) matrix input
          #   i.e. 3 and [[5,8,7,6],[1,3,2,4],[9,6,3,0]]
          #    → [[5,1,9],[8,3,6],[7,2,3],[6,4,0]]
Σ    }    # Sort the rows of this matrix by:
 ¹Ä       #  Take the absolute value of the input
          #   i.e. -3 → 3
   <      #  Decreased by 1 to make it 0-indexed
          #   i.e. 3 → 2
    è     #  And index it into the current row
          #   i.e. [5,8,7,6] and 2 → 7
          #   i.e. [5,1,9] and 2 → 9
          #  i.e. [[5,1,9],[8,3,6],[7,2,3],[6,4,0]] sorted by [9,6,3,0]
          #   → [[6,4,0],[7,2,3],[8,3,6],[5,1,9]]
          #  i.e. [[5,8,7,6],[1,3,2,4],[9,6,3,0]] sorted by [7,2,3]
          #   → [[1,3,2,4],[9,6,3,0],[5,8,7,6]]
¹di       # And if the integer input was positive:
   ø      #  Swap the rows and columns back again now that we've sorted them
          #   i.e. 3 and [[6,4,0],[7,2,3],[8,3,6],[5,1,9]]
          #    → [[6,7,8,5],[4,2,3,1],[0,3,6,9]]
          # (And implicitly output the now sorted matrix)
Kevin Cruijssen
fuente
1
Obtuve diø}Σ¹Ä<è]¹diøcuál es un subconjunto tuyo, así que no publicaré una respuesta por separado.
Emigna
@Emigna Dang, haces que parezca tan fácil ... Ahora que lo veo, no puedo creer que yo mismo no haya pensado en eso, pero es ingenioso al mismo tiempo ... ¡Gracias! La friolera de 10 bytes guardados gracias a ti.
Kevin Cruijssen
4

JavaScript (ES6), 90 bytes

t=m=>m[0].map((_,x)=>m.map(r=>r[x]))
f=(m,k)=>k<0?m.sort((a,b)=>a[~k]-b[~k]):t(f(t(m),-k))

Pruébalo en línea!

¿Cómo?

JS no tiene un método de transposición nativo, por lo que debemos definir uno:

t = m =>              // given a matrix m[]
  m[0].map((_, x) =>  // for each column at position x in m[]:
    m.map(r =>        //   for each row r in m[]:
      r[x]            //     map this cell to r[x]
    )                 //   end of map() over rows
  )                   // end of map() over columns

Función principal:

f = (m, k) =>         // given a matrix m[] and an integer k
  k < 0 ?             // if k is negative:
    m.sort((a, b) =>  //   given a pair (a, b) of matrix rows, sort them:
      a[~k] - b[~k]   //     by comparing a[-k - 1] with b[-k - 1]
    )                 //   end of sort
  :                   // else:
    t(f(t(m), -k))    //   transpose m, call f() with -k and transpose the result

k=2

M=(587613249630)t(M)=(519836723640)f(t(M),2)=(519723836640)f(M,2)=t(f(t(M),2))=(578612349360)
Arnauld
fuente
3

MATL , 17 bytes

y0>XH?!]w|2$XSH?!

Pruébalo en línea!

O verificar todos los casos de prueba

Explicación

y       % Implicit inputs: number n, matrix M. Duplicate from below: pushes n, M, n
0>      % Greater than 0?
XH      % Copy into clipboard H
?       % If true
  !     %   Transpose matrix. This way, when we sort the rows it will correspond
        %   to sorting the columns of the original M
]       % End
w       % Swap: moves n to top
|       % Absolute value
2$XS    % Two-input sortrows function: sorts rows by specified column
H       % Push contents from clipboard H
?       % If true
  !     %   Transpose again, to convert rows back to columns
        % Implicit end
        % Implicit display
Luis Mendo
fuente
2

Python 2 , 71 70 bytes

f=lambda m,n:n<0and sorted(m,key=lambda l:l[~n])or zip(*f(zip(*m),-n))

Pruébalo en línea!


Si nes negativo, las filas se ordenan según la columna n.

De lo contrario, la matriz se transpone, se ordena de la misma manera y se transpone nuevamente.

TFeld
fuente
1

C # (.NET Core) , 186 bytes

(x,y)=>{Func<int[][],int[][]>shift=a=> a[0].Select((r,i)=>a.Select(c=>c[i]).ToArray()).ToArray();return y>0?shift(shift(x).OrderBy(e=>e[y-1]).ToArray()):x.OrderBy(e=>e[-y-1]).ToArray();}

Pruébalo en línea!

Sin golf:

    private static int[][] Blocksort0a(int[][] array, int sortingInstruction)
    {
        Func<int[][], int[][]> shift = a => a[0].Select((r, i) => a.Select(c => c[i]).ToArray()).ToArray();

        sortingInstruction++;

        array = sortingInstruction < 0 ? 
        shift(shift(array).OrderBy(e => e[-sortingInstruction]).ToArray()) 
             : 
        array.OrderBy(e => e[sortingInstruction]).ToArray();

        return null;
    }

La función shift la usaremos dos veces, por lo que una variable de función ahorrará espacio. La función itera a través de la dimensión horizontal de la matriz en el índice y agrega cada elemento en ese índice de cada matriz horizontal a una nueva matriz de salida (horizontalmente), muy similar a la solución JS de Arnoud.

Ahora el orden es simple, ordene la matriz horizontal por número en el índice (argumento -1), opcionalmente desplazando la matriz antes y después de la clasificación.

Visto cómo la pregunta habla específicamente de arreglos, los convertimos a arreglos varias veces (muy, muy derrochador). Sentirse un poco tonto por usar un lenguaje tan detallado en el código de golf jeje.

Barodus
fuente
1

C # (.NET Core) , 142/139 138/135 bytes (y otro -1 más por Kevin)

(a,s)=>s<0?a.OrderBy(e=>e[~s]).ToArray():a.Select(f=>a[s-1].Select((v,j)=>new{v,j}).OrderBy(e=>e.v).Select(e=>f[e.j]).ToArray()).ToArray()

Pruébalo en línea!

Sin golf:

    private static int[][] Blocksort0b(int[][] array, int sortingInstruction)
    {
        if (sortingInstruction < 0) { return array.OrderBy(e => e[-sortingInstruction - 1]).ToArray(); }
        var rowIndices = array[sortingInstruction - 1].Select((value, index) => (value, index)).OrderBy(e => e.value);
        var newRow = new int[array[0].Length];
        for (var i = 0; i < array.Length; i++)
        {
            int horizontalIndexer = 0;
            foreach (var e in rowIndices)
            {
                newRow[horizontalIndexer++] = array[i][e.index];
            }
            array[i] = newRow.ToArray();
        }
        return array;
    }

Nuevo enfoque todo en línea; la respuesta negativa todavía ordena las matrices por elemento en el índice. De lo contrario, se crea una colección de value-index-pair del array-at-index y se ordena por valor. Esto crea efectivamente una colección de índices en orden de tener que ser agregado. Luego, para cada conjunto, se seleccionan los elementos en las posiciones predeterminadas. Bastante recorte de código y feo, feo, feo ** sollozos silenciosos ** implica la reutilización de los parámetros de entrada, y ahí tienes ... 142 bytes.

Nuevamente, el argumento de matrices se aplica estrictamente, agregando bastante sobrecarga para las llamadas .ToArray ().

Reclamación de 135 bytes, ¿eh? Las tuplas de valor inferido de C # 7.2 recortarían tres bytes adicionales, pero tio.run no lo permite. Por lo tanto, esta es la respuesta que decidí publicar para una fácil verificación.

Barodus
fuente
1
Buena respuesta. Hay algunas cosas pequeñas para el golf. (a,s)=>Puede ser un curry a=>s=>. (s<0)?no necesita el paréntesis, y -s-1puede serlo ~s. Pruébelo en línea: 137 bytes
Kevin Cruijssen
¡Dulce! Nunca hubiera dejado que la función volviera a funcionar para salvar a un personaje, estoy gratamente sorprendido. ¡Gracias! También un caso fuerte de descaradamente pasar por alto el operador no y paréntesis. Actualicé el not y los paréntesis, pero les dejaré todo el honor por la función-return-function.
Barodus
1

Java (OpenJDK 8) , 326 bytes

(a,b)->{int l=a.length,w=a[0].length,k,m,t,i;if(b>0){for(i=0;i<w;i++){for(k=1;k<(w-i);k++){if(a[b-1][k-1]>a[b-1][k]){for(m=0;m<l;m++){t=a[m][k];a[m][k]=a[m][k-1];a[m][k-1]=t;}}}}}else{b*=-1;for(i=0;i<l;i++){for(k=1;k<(l-i);k++){if(a[k-1][b-1]>a[k][b-1]){for(m=0;m<w;m++){t=a[k][m];a[k][m]=a[k-1][m];a[k-1][m]=t;}}}}}return a;}

Pruébalo en línea!

Bueno, muchachos, esta pregunta fue muy frustrante para mí, y publiqué mi respuesta SABIENDO que estaba olvidando algo, afortunadamente tenemos leyendas como Kevin Cruijssen aquí para ayudarnos :)

Java (OpenJDK 8) , 281 bytes

a->b->{int l=a.length,w=a[0].length,k,m,t,i;if(b>0)for(i=0;i<w;i++)for(k=0;++k<w-i;)for(m=0;a[b-1][k-1]>a[b-1][k]&m<l;a[m][k]=a[m][k-1],a[m++][k-1]=t)t=a[m][k];else for(b*=-1,i=0;i<l;i++)for(k=0;++k<l-i;)for(m=0;a[k-1][b-1]>a[k][b-1]&m<w;a[k][m]=a[k-1][m],a[k-1][m++]=t)t=a[k][m];}

Pruébalo en línea!

X1M4L
fuente
Todavía no he visto el algoritmo real, pero puede guardar 35 bytes eliminando todos los corchetes y colocando todo dentro de los bucles (incluida la instrucción if interna). Pruébelo en línea: 291 bytes EDITAR: Aquí con sangrías de espacio para que pueda ver más claramente los cambios que hice.
Kevin Cruijssen
@KevinCruijssen Sabía que me faltaba algo
X1M4L
Además, puede convertirlo en una entrada de curry en a->b->lugar de (a,b)->eliminar la returndeclaración, ya que está modificando la matriz de entrada. 281 bytes Sin embargo, sigue siendo una buena respuesta. +1 de mi parte Hice el desafío en 05AB1E, pero esta vez ni siquiera lo habría probado en Java. ;)
Kevin Cruijssen
270 bytes
ceilingcat
1

Kotlin , 192 bytes

{m:Array<Array<Int>>,s:Int->if(s<0){m.sortBy{it[-s-1]}}else{val a=Array(m[0].size){c->Array(m.size){m[it][c]}}
a.sortBy{it[s-1]}
(0..m.size-1).map{r->(0..m[0].size-1).map{m[r][it]=a[it][r]}}}}

Pruébalo en línea!

JohnWells
fuente
1

Rojas , 190 185 bytes

func[b n][t: func[a][c: length? a/1 a: to[]form a
d: copy[]loop c[append/only d extract a c take a]d]d: does[if n > 0[b: t b]]d
m: absolute n sort/compare b func[x y][x/(m) < y/(m)]d b]

Pruébalo en línea!

Explicación:

f: func [ b n ] [
    t: func [ a ] [                            ; helper transpose function 
        c: length? a/1                         ; c is the length of the rows
        a: to-block form a                     ; flatten the list
        d: copy []                             ; an empty block (list)
        loop c [                               ; do as many times as the number of columns  
            append/only d extract a c          ; extract each c-th element (an entire column)
                                               ; and append it as a sublist to d
            take a                             ; drop the first element
        ] 
        d                                      ; return the transposed block (list of lists)
    ]
   d: does [ if n > 0 [ b: t b ] ]             ; a helper function (parameterless) to transpose 
                                               ; the array if positive n
   d                                           ; call the function  
   m: absolute n                               ; absolute n
   sort/compare b func[ x y ] [ x/(m) < y/(m) ]; sort the array according to the chosen column 
   d                                           ; transpose if positive n
   b                                           ; return the array  
]

Mi solución real es de 175 bytes de largo, pero no funciona en TIO. Aquí está, trabajando normalmente en la consola roja:

Rojo , 175 bytes

func[b n][d: does[if n > 0[c: length? b/1 a: to-block form b
t: copy[]loop c[append/only t extract a c take a]b: t]]d
m: absolute n sort/compare b func[x y][x/(m) < y/(m)]d b]
Galen Ivanov
fuente
0

VBA (Excel), 205 bytes

¡Hurra! ¡Segundo conteo de bytes más largo! No perdí por completo: D

Golfizado:

Sub d(a)
With ActiveSheet.Sort
  .SortFields.Clear
  .SortFields.Add Key:=IIf(a<0,ActiveSheet.Columns(Abs(a)),ActiveSheet.Rows(Abs(a)))
  .SetRange ActiveSheet.UsedRange
  .Orientation=IIf(a<0,1,2)
  .Apply
End With
End Sub

Esto ordena todos los datos en la hoja de trabajo abierta (activa) usando UsedRange ... que puede tener errores, pero solo debe contener celdas que se hayan editado.

Sin golf:

Sub d(a)
  'Clear any Sort preferences that already exists
  ActiveSheet.Sort.SortFields.Clear
  'Use the column if A is negative, the row if A is positive
  ActiveSheet.Sort.SortFields.Add Key:=IIf(a < 0, ActiveSheet.Columns(Abs(a)), ActiveSheet.Rows(Abs(a)))
  'Set the area to sort
  ActiveSheet.Sort.SetRange ActiveSheet.UsedRange
  'Orient sideways if sorting by row, vertical if by column
  ActiveSheet.Sort.Orientation = IIf(a < 0, xlTopToBottom, xlLeftToRight)
  'Actually sort it now
  ActiveSheet.Sort.Apply
End Sub
seadoggie01
fuente
Si supone que la hoja activa es sheet1, puede reducir esto a 169 bytes comoSub d(a) With Sheet1.Sort .SortFields.Clear .SortFields.Add IIf(a<0,Columns(Abs(a)),Rows(Abs(a))) .SetRange Sheet1.UsedRange .Orientation=(a<0)+2 .Apply End With End Sub
Taylor Scott,
Además, creo que puede suponer con seguridad que no hay .SortFieldsDefinido, por lo que también puede eliminar la .Sortfields.Clearlínea.
Taylor Scott
0

Perl 6 , 43 bytes

{($!=$_>0??&[Z]!!*[])o*.sort(*[.abs-1])o$!}

Pruébalo en línea!

Función curry

Explicación

{                                         } # Block returning function composed of
                                       o$!  # 1. Apply $! (transpose or not)
                     o*.sort(*[.abs-1])     # 2. Sort rows by column abs(i)-1
     $_>0??&[Z]                             # 3. If i > 0 transpose matrix
               !!*[]                        #    Else identity function
 ($!=               )                       #    Store in $!
nwellnhof
fuente
0

Physica , 45 bytes

Muy similar a la respuesta JS de Arnauld .

F=>n;m:n<0&&Sort[->u:u{~n};m]||Zip@F#Zip@m#-n

Pruébalo en línea!

¿Cómo funciona?

Se puede encontrar una explicación más elaborada y visual en la respuesta vinculada.

F=>n;m:           // Create a function F that takes two arguments, n and m.
       n<0&&      // If n < 0 (i.e. is negative)
Sort[->u{~n};m]   // Sort the rows u of m by the result of the function u[~n].
                  // In short, sort by indexing from the end with n.
||    F#Zip@m#-n  // Else, apply F to Zip[m] and -n. Uses a new feature, binding.
  Zip@            // And transpose the result.
Sr. Xcoder
fuente
0

J , 32 bytes

f=.[/:({"1~<:)
g=.(f&.|:|)`f@.(0<])

Pruébalo en línea!

Nota la g=. del verbo principal no cuenta.

Una versión explícita para los mismos bytes.

J , 32 bytes

4 :'y(]/:{"1)&.(|:^:(x<0))~<:|x'

Pruébalo en línea!

Jonás
fuente
0

Clojure, 91 bytes

(fn f[A i](if(< i 0)(sort-by #(nth %(- -1 i))A)(apply map list(f(apply map list A)(- i)))))

Argh, apply map list* 2.

NikoNyrh
fuente