Ordenar una lista

26

Resumen

Dada una lista de enteros, devuelve el índice en el que terminaría cada entero cuando se ordenara.

Por ejemplo, si la lista era [0,8,-1,5,8], debería regresar [1,3,0,2,4]. Tenga en cuenta que los dos 8s mantienen su orden entre sí (el orden es estable).

Dicho de otra manera: para cada elemento de la lista, devuelva el número de elementos en la lista que son: Menor que el elemento elegido O (igual al elemento Y aparece antes del elemento elegido)

Los índices deben comenzar con 0 (no 1) EDITAR: dado el gran retroceso, permitiré indicios basados ​​en 1.

Casos de prueba:

0                -> 0
23               -> 0
2,3              -> 0,1
3,2              -> 1,0
2,2              -> 0,1
8,10,4,-1,-1,8   -> 3,5,2,0,1,4
0,1,2,3,4,5,6,7  -> 0,1,2,3,4,5,6,7
7,6,5,4,3,2,1,0  -> 7,6,5,4,3,2,1,0
4,4,0,1,1,2,0,1  -> 6,7,0,2,3,5,1,4
1,1,1,1,1,1,1,1  -> 0,1,2,3,4,5,6,7
1,1,1,1,1,1,1,0  -> 1,2,3,4,5,6,7,0
Nathan Merrill
fuente
A pesar de la sencillez de este desafío, no pude encontrar un duplicado de este desafío.
Nathan Merrill
1
Esta es una especialización de esta pregunta donde, en lugar de tomar dos matrices, toma una matriz y la segunda es [0 1 ... n-1].
Peter Taylor
@PeterTaylor: en ese desafío, la matriz no tiene repeticiones.
Lynn
2
Nota para los solucionadores: ese 8,10,4,-1,-1caso de prueba es muy engañoso. Prueba el 4,4,0,1,1,2,0,1primero.
Lynn
@ Lynn Miré hacia arriba lo que hace "subir de nivel", y descubrí por qué ese caso de prueba es tan engañoso. Fijo.
Nathan Merrill

Respuestas:

21

APL, 2 bytes

⍋⍋

El "subir de grado" incorporado, aplicado dos veces. Funciona si la indexación comienza en 0, que no es el valor predeterminado para todos los tipos de APL. Pruébalo aquí!

¿Por qué funciona esto?

⍋xdevuelve una lista de índices que lo haría de manera estable especiex . Por ejemplo:

    x ← 4 4 0 1 1 2 0 1
    ⍋x
2 6 3 4 7 5 0 1

porque si tomas elemento 2, 6entonces 3... entonces obtienes una lista ordenada establemente:

    x[⍋x]
0 0 1 1 1 2 4 4

Pero la lista de índice que responde a esta pregunta es sutilmente diferente: primero queremos el índice del elemento más pequeño, luego el segundo más pequeño, etc., nuevamente, manteniendo el orden original.

Sin ⍋xembargo, si miramos, vemos que puede darnos esta lista fácilmente: la posición de un 0in ⍋xnos dice dónde terminaría el elemento más pequeño después de la clasificación, y la posición de un 1in ⍋xnos dice dónde terminaría el segundo elemento más pequeño etc.

Pero sabemos que ⍋xcontiene exactamente los números [0, 1 ... n − 1] . Si lo calificamos nuevamente , solo obtendremos el índice de 0in ⍋x, luego el índice de 1in ⍋x, etc., que es precisamente lo que nos interesa.

Entonces la respuesta es ⍋⍋x.

Lynn
fuente
wow, esto debe haber sido minuciosamente jugado: P
Downgoat
ngn-apl solo admite UTF-8, pero esto funciona en casi todos los sabores, siempre que el origen del índice esté establecido en 0.
Dennis
Eso me hace preguntarme: ¿hay alguna prueba en línea para los sabores APL clásicos?
Lynn
Hay TryAPL para Dyalog, pero el valor predeterminado de IO es 1. Sin embargo, es fácilmente modificable. Enlace permanente
Dennis
1-based está permitido ahora.
Nathan Merrill
6

JavaScript ES6, 87 82 79 74 70 bytes

(a,b={})=>a.map(l=>[...a].sort((a,b)=>a-b).indexOf(l)+(b[l]=b[l]+1|0))

No me gusta usar un objeto, pero parece ser la forma más corta de hacer un seguimiento de los engañados

Explicación

(a,b={})=>          `a` is input
                    `b` stores the occurrences of each number
  a.map(l =>        Loop over the array, `l` is item
  [...a]            Copy `a`
    .sort(...)       Sort in ascending numerical order
    .indexOf(l)      Index of input in that array
  +                 Add the following to account for dupes
   (b[l]=            set and return the item `l` in hashmap `b` to...
     b[l]+1           Increase the counter by one if it exists yet
     |0               default is zero
   )
Downgoat
fuente
61 bytes
Arnauld
6

K , 5 2 bytes

<<

Sube de nivel ( <) dos veces. ¡JohnE ahorró tres bytes al señalar que existen expresiones tácitas en K! Super guay. Pruébalo.

Lynn
fuente
El envoltorio lambda no es estrictamente necesario, simplemente puede escribir esto como una expresión tácita <<. Probar aquí .
JohnE
5

Haskell, 50 48 bytes

import Data.List
m x=map snd$sort$zip x[0..]
m.m

Ejemplo de uso: m.m $ [4,4,0,1,1,2,0,1]-> [6,7,0,2,3,5,1,4].

Se map snd.sort.zip x [0..]aplica dos veces en la entrada, es decir, empareja cada elemento e con su índice i ( (e,i)), ordena y elimina los primeros elementos. Repite una vez.

A @Lynn se le ocurrió m=map snd.sort.(`zip`[0..])que tiene el mismo número de bytes.

nimi
fuente
5

Python 2, 67 60 bytes

def f(x):x=zip(x,range(len(x)));print map(sorted(x).index,x)

¡Gracias a @xnor por jugar golf en 7 bytes!

Pruébalo en Ideone .

Dennis
fuente
La movida de un tirón enumeratese puede hacer más corto con un zip: l=input();x=zip(l,range(len(l))).
xnor
En ese caso, una función es aún más corta. ¡Gracias!
Dennis
4

PowerShell v2 +, 63 bytes

param($n)$n|%{($n|sort).IndexOf($_)+($n[0..$i++]-eq$_).count-1}

Toma entrada $n, canaliza eso a través de un bucle sobre cada elemento |%{...}. Cada iteración, nosotros sort $ny obtener el IndexOfnuestro elemento actual $_. Esto cuenta cuántos elementos son más pequeños que el elemento actual. Agregamos a eso una porción de $n, que expande cada iteración de bucle, de los elementos que son iguales al elemento actual $_y toman el .Countde eso. Luego restamos -1para no contar nuestro elemento actual, y ese número queda en la tubería. La salida al final es implícita.

Ejemplos

PS C:\Tools\Scripts\golfing> .\ordering-a-list.ps1 @(4,4,0,1,1,2,0,1)
6
7
0
2
3
5
1
4

PS C:\Tools\Scripts\golfing> .\ordering-a-list.ps1 @(8,10,4,-1,-1)
3
4
2
0
1
AdmBorkBork
fuente
4

CJam, 15 bytes

{{eeWf%$1f=}2*}

Pruébalo en línea!

Explicación

{             }       Delimits an anonymous block.
 {         }2*        Run this block on the argument twice:
  ee                  Enumerate ([A B C] → [[0 A] [1 B] [2 C]])
    Wf%               Reverse each ([[A 0] [B 1] [C 2]])
       $              Sort the pairs lexicographically;
                        i.e. first by value, then by index.
        1f=           Keep the indices.
Lynn
fuente
4

J, 5 bytes

/:^:2

Sube de categoría ( /:) dos veces (^:2 ). 0 indexado.

Para probarlo, escribir f =: /:^:2y luego f 4 4 0 1 1 2 0 1en tryj.tk .

Lynn
fuente
O /:@/:con un recuento de bytes igual.
Leaky Nun
4

MATL, 10 9 4 bytes

4 bytes guardados gracias a @Luis

&S&S

Esta solución utiliza indexación basada en 1

Pruébalo en línea

Suever
fuente
@DrGreenEggsandIronMan Busco meta y no pude encontrar nada que indique de ninguna manera. Dicho esto, he revertido la restricción.
Nathan Merrill
4

05AB1E, 12 bytes

2FvyN‚}){€¦˜

Explicado

2F            # 2 times do
  vyN‚})      # create list of [n, index]-pairs
        {€¦   # sort and remove first element leaving the index
           ˜  # deep flatten
              # implicit output

Pruébalo en línea

Emigna
fuente
4

Python 2, 67 bytes

a=input()
p=[]
for x in a:print sorted(a).index(x)+p.count(x);p+=x,

xnor guardó dos bytes.

Lynn
fuente
Es más corto para volver a crear la lista de elementos vistos anteriormente sobre la marcha:a=input();p=[]\nfor x in a:print sorted(a).index(x)+p.count(x);p+=x,
XNOR
Ah, eso me gusta! Gracias.
Lynn
4

Haskell, 40 bytes

f l|z<-zip l[0..]=[sum[1|y<-z,y<x]|x<-z]

Anote cada elemento con su índice, luego asigne cada elemento al recuento de elementos más pequeños, rompiendo el empate en el índice. Sin clasificación

xnor
fuente
3

Julia, 17 bytes

~=sortperm;!x=~~x

1 indexado. Sube de nivel ( sortperm) dos veces.Pruébalo aquí

EDITAR: ¡Dennis ahorró cuatro bytes dando nombres de operadores! Julia es rara.

Lynn
fuente
3

JavaScript (ES6), 52 bytes

a=>(g=a=>[...a.keys()].sort((n,m)=>a[n]-a[m]))(g(a))

Se define gcomo la función de calificación, que devuelve una matriz de índices de la cual todos los elementos de la matriz ordenada habrían venido de la matriz original. Lamentablemente, lo que queremos son los índices a los que irán todos los elementos. Afortunadamente, esto resulta ser el mapeo de la calificación a la lista original de índices, que en sí misma puede considerarse el resultado de la clasificación de la calificación, lo que nos permite tomar la calificación de la calificación para lograr el resultado deseado.

Neil
fuente
3

Pyth, 10 9 bytes

1 byte gracias a Jakube.

xLo@QNUQU

Banco de pruebas.

No debe ser un camino más corto ...

Monja permeable
fuente
xLen lugar de sxR. ¿O estoy pasando por alto algo?
Jakube
@Jakube ¡Gracias!
Leaky Nun
2

Raqueta, 117 bytes

(λ(x)(build-list(length x)(λ(h)((λ(y)(+(count(λ(z)(< z y))x)(count(λ(z)(eq? z y))(take x h))))(list-ref x h)))))

Estoy eternamente decepcionado por la falta de un proyecto incorporado para esto.

Steven H.
fuente
¿Sería más corto poner cada elemento en un par (número, índice) y luego ordenarlo?
Nathan Merrill
Lo intenté, pero me da el inverso de la lista que quisiera, y desafortunadamente obtener el índice de un objeto dentro de la lista para invertirlo es terriblemente ineficiente.
Steven H.
2

Ruby, 54 53 bytes

Pruébalo en línea

-1 byte de la actualización al enfoque de @ Downgoat de usar un hash para almacenar valores en lugar de contar los duplicados cada vez.

->a{b={};a.map{|e|a.sort.index(e)+b[e]=(b[e]||-1)+1}}
Tinta de valor
fuente
El tipo de Ruby es inestable , lo que significa que esto podría hacer algo incorrecto en los lazos.
Nathan Merrill
1
@NathaMerrill No lo hace por el método exacto que estoy usando para generar los números. Si clasifico en una lista de índices, produciría el resultado incorrecto. Prueba el enlace! Funcionará el 60% del tiempo, siempre. Publicaré una explicación más adelante, también.
Value Ink
Ah ok No estaba seguro de lo que está haciendo el resto del código (no sé Ruby)
Nathan Merrill
? No hace lo incorrecto en los lazos, pero hace algo mal el 40% del tiempo.
WGroleau
@WGroleau es una cita de Anchorman. Sin embargo, mi código funciona todo el tiempo.
Value Ink
2

Clojure, 83 bytes

(fn[a](nth(iterate #(->> %(map-indexed(comp vec rseq vector))sort(map second))a)2))

Creo una función anónima que califica la matriz de entrada y la repite dos veces en la entrada. La primera llamada devolverá la calificación. La segunda llamada opera en la calificación y devuelve el rango.

millas
fuente
2

Brachylog , 27 bytes

lL-M,?og:MjO,L~l.#d:Orz:ma?

Pruébalo en línea! o verificar todos los casos de prueba .

Explicación

Esta es una implementación sencilla de la siguiente relación: cada entero de la salida correspondiente a un elemento de la entrada es el índice de ese elemento en la entrada ordenada.

Example input: [3:2]

lL               L is the length of the input (e.g L=2)
  -M,            M = L-1 (e.g. M=1)
?o               Sort the input...
  g:MjO,         ... and create a list O with L copies of the input (e.g. O=[[2:3]:[2:3]])
L~l.             Output is a list of length L (e.g. [I:J])
    #d           All elements of the output must be distinct (e.g. I≠J)
      :Orz       Zip O with the output (e.g. [[[2:3]:I]:[[2:3]:J]])
          :ma?   Apply predicate Member with that zip as input and the input as output
                 (e.g. 3 is the Ith element of [2:3] and 2 is the Jth element of [2:3])
Fatalizar
fuente
2

Mathematica, 15 bytes

(o=Ordering)@*o
alephalpha
fuente
2

Mathematica, 135 bytes

Function[{list}, SortBy[MapIndexed[Join[{#1}, #2]&, Sort@MapIndexed[Join[{#1}, #2] &, list]], #[[1, 2]] &][[All, 2]] - 1]
navigaid
fuente
1

Lisp común, 117 bytes

(flet((i(Z)(mapcar'cdr(stable-sort(loop for e in Z for x from 0 collect(cons e x))'< :key'car))))(lambda(L)(i(i L))))

Aplicar una transformación de Schwartz dos veces.

;; FIRST TIME

(0 8 -1 5 8)
;; add indexes
((0 . 0) (8 . 1) (-1 . 2) (5 . 3) (8 . 4))
;; sort by first element
((-1 . 2) (0 . 0) (5 . 3) (8 . 1) (8 . 4))
;; extract second elements
(2 0 3 1 4)

;; SECOND TIME

(2 0 3 1 4)
;; indexes
((2 . 0) (0 . 1) (3 . 2) (1 . 3) (4 . 4))
;; sort by first element
((0 . 1) (1 . 3) (2 . 0) (3 . 2) (4 . 4))
;; extract second elements
(1 3 0 2 4)

Prueba

(let ((fn (flet((i(Z)(mapcar'cdr(stable-sort(loop for e in Z for x from 0 collect(cons e x))'< :key'car))))(lambda(L)(i(i L))))))
  (every
   (lambda (test expected)
     (equal (funcall fn test) expected))

   '((0) (23) (2 3) (3 2) (2 2) (8 10 4 -1 -1 8) (0 1 2 3 4 5 6 7)
     (7 6 5 4 3 2 1 0) (4 4 0 1 1 2 0 1) (1 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 0))

   '((0) (0) (0 1) (1 0) (0 1) (3 5 2 0 1 4) (0 1 2 3 4 5 6 7) (7 6 5 4 3 2 1 0)
     (6 7 0 2 3 5 1 4) (0 1 2 3 4 5 6 7) (1 2 3 4 5 6 7 0))))
=> T
volcado de memoria
fuente
1

JavaScript (usando una biblioteca externa) (105 bytes)

(n)=>{var a=_.From(n).Select((v,i)=>v+""+i);return a.Select(x=>a.OrderBy(y=>(y|0)).IndexOf(x)).ToArray()}

Enlace a lib: https://github.com/mvegh1/Enumerable Explicación del código: Cree un método anónimo que acepte una lista de enteros. _.Desde crea una instancia de la biblioteca que envuelve una matriz con métodos especiales. Seleccione asigna cada elemento a un nuevo elemento, tomando el alor "v", analizándolo en una cadena y luego concatenando el índice "i" de ese elemento (esto resuelve el caso de valores duplicados). Eso se almacena en la variable 'a'. Luego devolvemos el resultado de lo siguiente: Asigna cada elemento en 'a' al índice de ese elemento en la versión ordenada de a (como enteros), y vuelve a convertirlo en una matriz JS nativa

ingrese la descripción de la imagen aquí

Tenga en cuenta que los números duplicados negativos parecen imprimirse en el orden inverso. No estoy seguro si eso invalida esta solución? Técnicamente 8,10,4, -1, -1,8 deberían ser 3,5,2,0,1,4 según OP, pero mi código está imprimiendo 3,5,2,1,0,4, que creo que es ¿sigue siendo técnicamente válido?

applejacks01
fuente
1

GNU Core Utils, 39 33 bytes

nl|sort -nk2|nl|sort -nk2|cut -f1

Produce una salida basada en 1. Agregar -v0después del segundonl para obtener una salida basada en 0. (+4 bytes)

Comandos que estamos usando:

  • nl agrega números de línea a cada línea de la entrada.
  • sort -n -k 2 ordena por columna 2 numéricamente.
  • cut -f 1 toma la primera columna delimitada por tabulaciones, descartando el resto.

Además, el -s se puede pasar opción a sortpara solicitar una ordenación estable, pero no la necesitamos aquí. Si dos elementos son idénticos, sortdeterminará su orden volviendo a las otras columnas, que en este caso es la salida monotónicamente creciente de nl. Por lo tanto, la ordenación será estable sin necesidad de especificarlo, en virtud de la entrada.

joeytwiddle
fuente
1

Java 149 140 bytes

public int[] indexArray(int[] index){
  int[] out=new int[index.length];
  for(int i=-1;++i<index.length;){
    for(int j=-1;++i<index.length;){
      if(index[i]==Arrays.sort(index.clone())[j]){
        out[i]=j;
      }
    }
  }
  return out;
}

Golfed

int[]a(int[]b){int l=b.length;int[]o=new int[l];for(int i=-1;++i<l;)for(int j=-1;++i<l;)if(b[i]==Arrays.sort(b.clone())[j])o[i]=j;return o;}

Gracias a @Kevin Cruissjen por el afeitado de 9 bytes.

Roman Gräf
fuente
@Nathan Merrill Me di cuenta de eso cuando jugué al golf, pero lo olvidé cuando pegué la respuesta al golf.
Roman Gräf
1
Puedes jugar al golf un poco más. No necesitas los espacios entre int[] ay int[] b. Puedes sacar intlos bucles. Y como lo usa b.lengthdos veces al principio, puede colocarlo en un campo separado. Entonces, en total, algo como esto: int[]a(int[]b){int l=b.length,o[]=new int[l],i,j;for(i=-1;++i<l;)for(j=-1;++i<b.length;)if(b[i]==Arrays.sort(b.clone())[j])o[i]=j;return o;}( 140 bytes ) Hmm, además, no parece funcionar ...Arrays.sort(...) no devuelve nada (es un voidmétodo), entonces, ¿cómo puedes compararlo con b[i]...?
Kevin Cruijssen
1

PHP, 88 bytes

unset($argv[0]);$a=$argv;sort($a);foreach($argv as$e)echo$h[$e]+++array_search($e,$a),_;

opera en argumentos de línea de comando; imprime una lista separada por guiones bajos y con índice 0. Corre con-nr .

Descompostura

unset($argv[0]);        // remove file name from arguments
$a=$argv;               // create copy
sort($a);               // sort copy (includes reindexing, starting with 0)
foreach($argv as$e)     // loop $e through original
    echo                    // print:
        $h[$e]++            // number of previous occurences
        +array_search($e,$a)// plus position in copy 
        ,_                  // followed by underscore
    ;
Titus
fuente
0

MATLAB, 29 bytes

function j=f(s);[~,j]=sort(s)

La mayoría de las funciones integradas de ordenación de MATLAB devolverán una segunda matriz opcional que contiene los índices ordenados. losj= podrían eliminarse si la impresión de los índices es aceptable, en lugar de devolverlos.

MattWH
fuente
0

CJam , 19 bytes

_$:A;{A#_AWt:A;1+}%

Pruébalo en línea!

Explicación:

_ duplicate array
 $ sort array
  :A store in variable A
    ; discard top item in stack
     {A#_AWt:A;1+} block that finds index of item and removes it from sorted array to prevent duplicates
      % map block onto every item in array
lolad
fuente