Memesan daftar

26

Ringkasan

Diberikan daftar bilangan bulat, kembalikan indeks setiap bilangan bulat akan berakhir pada saat diurutkan.

Misalnya, jika daftar itu [0,8,-1,5,8], Anda harus kembali [1,3,0,2,4]. Perhatikan bahwa keduanya 8mempertahankan urutan relatif satu sama lain (pengurutannya stabil).

Dengan kata lain: Untuk setiap elemen dalam daftar, kembalikan jumlah elemen dalam daftar yang: Lebih kecil dari elemen yang dipilih ATAU (sama dengan elemen DAN muncul sebelum elemen yang dipilih)

Indeks harus dimulai dengan 0 (bukan 1) EDIT: mengingat pushback besar, saya akan mengizinkan indeks berbasis 1.

Kasus uji:

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
sumber
Terlepas dari kesederhanaan tantangan ini, saya tidak dapat menemukan duplikat dari tantangan ini.
Nathan Merrill
1
Ini adalah spesialisasi dari pertanyaan ini di mana alih-alih mengambil dua array dibutuhkan satu array dan yang kedua adalah [0 1 ... n-1].
Peter Taylor
@PeterTaylor: Dalam tantangan itu, array tidak memiliki pengulangan.
Lynn
2
Catatan untuk solver: bahwa 8,10,4,-1,-1test case sangat menipu. Coba yang 4,4,0,1,1,2,0,1pertama.
Lynn
@ Lynn saya mencari tahu apa yang dilakukan "naik kelas", dan saya mencari tahu mengapa ujian itu begitu menipu. Tetap.
Nathan Merrill

Jawaban:

21

APL, 2 byte

⍋⍋

Built-in "naik", diterapkan dua kali. Bekerja jika pengindeksan dimulai pada 0, yang bukan merupakan standar untuk semua rasa APL. Coba di sini!

Mengapa ini bekerja?

⍋xmengembalikan daftar indeks yang akan diurutkan secara stabilx . Sebagai contoh:

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

karena jika Anda mengambil elemen 2, maka 6, maka 3... Anda mendapatkan daftar yang diurutkan secara stabil:

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

Tetapi daftar indeks yang menjawab pertanyaan ini agak berbeda: pertama kita ingin indeks elemen terkecil, lalu terkecil terkecil, dll - lagi-lagi, menjaga urutan aslinya.

Jika kita melihat ⍋x, meskipun, kita melihat hal itu dapat memberi kita daftar ini dengan mudah: yang posisi dari 0dalam ⍋xmemberitahu kita di mana elemen terkecil akan berakhir setelah menyortir, dan posisi dari 1dalam ⍋xmemberitahu kita di mana elemen terkecil kedua akan berakhir , dll.

Tapi kita tahu ⍋xpersis mengandung angka [0, 1 ... n − 1] . Jika kita nilai lagi , kita hanya akan mendapatkan indeks 0masuk ⍋x, lalu indeks 1masuk ⍋x, dll., Itulah tepatnya yang kita minati.

Jadi jawabannya adalah ⍋⍋x.

Lynn
sumber
wow, ini pasti
golf dengan
ngn-apl hanya mendukung UTF-8, tetapi ini bekerja di hampir semua rasa asalkan asal indeks diatur ke 0.
Dennis
Itu membuat saya bertanya-tanya: apakah ada try-it-online untuk rasa APL klasik?
Lynn
Ada TryAPL untuk Dyalog, tapi IO default ke 1. Ini mudah diubah. permalink
Dennis
Berbasis 1 diizinkan sekarang.
Nathan Merrill
12

Jelly, 2 byte

ỤỤ

Nilai naik dua kali. 1-diindeks. Cobalah online!

Lynn
sumber
Dua byte dalam skema pengkodean apa?
WGroleau
5
Ah! Di halaman kode Jelly . Saya menambahkan tautan di tajuk. :)
Lynn
6

JavaScript ES6, 87 82 79 74 70 byte

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

Tidak suka menggunakan objek tetapi tampaknya merupakan cara terpendek untuk melacak dupes

Penjelasan

(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
sumber
61 byte
Arnauld
6

K , 5 2 byte

<<

Tingkatkan ( <) dua kali. JohnE menyimpan tiga byte dengan menunjukkan ekspresi diam-diam yang ada di K! Sangat keren. Cobalah.

Lynn
sumber
Pembungkus lambda tidak sepenuhnya diperlukan - Anda hanya dapat menulis ini sebagai ekspresi diam-diam <<. Coba di sini .
JohnE
5

Haskell, 50 48 byte

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

Contoh penggunaan: m.m $ [4,4,0,1,1,2,0,1]-> [6,7,0,2,3,5,1,4].

Ini map snd.sort.zip x [0..]diterapkan dua kali pada input, yaitu memasangkan setiap elemen e dengan indeks i ( (e,i)), mengurutkannya menghapus elemen pertama. Ulangi satu kali.

@ Lynn datang dengan m=map snd.sort.(`zip`[0..])yang memiliki jumlah byte yang sama.

nimi
sumber
5

Python 2, 67 60 byte

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

Terima kasih kepada @xnor karena bermain golf 7 byte!

Uji di Ideone .

Dennis
sumber
Membalik enumeratedapat dilakukan lebih pendek dengan zip: l=input();x=zip(l,range(len(l))).
xnor
Dalam hal ini, suatu fungsi bahkan lebih pendek. Terima kasih!
Dennis
4

PowerShell v2 +, 63 byte

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

Mengambil input $n, menyalurkan melalui loop ke setiap elemen |%{...}. Setiap iterasi, kita sort $ndan dapatkan IndexOfelemen kita saat ini $_. Ini menghitung berapa banyak item lebih kecil dari elemen saat ini. Kami menambahkan bahwa sepotong $n, yang memperluas setiap iterasi loop, dari elemen yang sama dengan elemen saat ini $_dan mengambil .Countitu. Kami kemudian mengurangi -1sehingga kami tidak menghitung elemen kami saat ini, dan angka itu ditinggalkan di saluran pipa. Output pada akhirnya tersirat.

Contohnya

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
sumber
4

CJam, 15 byte

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

Cobalah online!

Penjelasan

{             }       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
sumber
4

J, 5 byte

/:^:2

Tingkatkan ( /:) dua kali (^:2 ). Diindeks 0.

Untuk mencobanya, ketik f =: /:^:2dan kemudian f 4 4 0 1 1 2 0 1ke tryj.tk .

Lynn
sumber
Atau /:@/:dengan jumlah byte yang sama.
Leaky Nun
4

MATL, 10 9 4 byte

4 Bytes disimpan berkat @Luis

&S&S

Solusi ini menggunakan pengindeksan berbasis 1

Cobalah secara Online

Suever
sumber
@DrGreenEggsandIronMan Saya mencari meta, dan saya tidak dapat menemukan apa pun yang menunjukkan cara mana pun. Yang mengatakan, saya telah mengembalikan batasan.
Nathan Merrill
4

05AB1E, 12 byte

2FvyN‚}){€¦˜

Dijelaskan

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

Cobalah online

Emigna
sumber
4

Python 2, 67 byte

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

xnatau menyimpan dua byte.

Lynn
sumber
Lebih pendek untuk membuat ulang daftar elemen yang sebelumnya terlihat saat Anda pergi:a=input();p=[]\nfor x in a:print sorted(a).index(x)+p.count(x);p+=x,
xnor
Ah, aku suka itu! Terima kasih.
Lynn
4

Haskell, 40 byte

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

Beri anotasi pada setiap elemen dengan indeksnya, lalu petakan setiap elemen dengan jumlah elemen yang lebih kecil, lalu buat indeks. Tidak ada penyortiran.

Tidak
sumber
3

Julia, 17 byte

~=sortperm;!x=~~x

1-diindeks. Tingkatkan ( sortperm) dua kali. Coba di sini.

EDIT: Dennis menyimpan empat byte dengan memberikan nama barang operator-y! Julia aneh.

Lynn
sumber
3

JavaScript (ES6), 52 byte

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

Tentukan gsebagai fungsi tingkat, yang mengembalikan array indeks tempat semua elemen dalam array yang diurutkan akan berasal dari dalam array asli. Sayangnya yang kita inginkan adalah indeks yang akan dituju semua elemen. Untungnya ini ternyata adalah pemetaan dari nilai kembali ke daftar indeks asli, yang dengan sendirinya dapat dianggap sebagai hasil dari penyortiran kelas, sehingga memungkinkan kita untuk mengambil nilai kelas untuk mencapai hasil yang diinginkan.

Neil
sumber
3

Pyth, 10 9 byte

1 byte berkat Jakube.

xLo@QNUQU

Suite uji.

Ada harus menjadi cara yang lebih pendek ...

Biarawati Bocor
sumber
xLbukannya sxR. Atau apakah saya mengabaikan sesuatu?
Jakube
@ Jakube Terima kasih!
Leaky Nun
2

Racket, 117 byte

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

Saya selalu kecewa dengan kurangnya builtin untuk ini.

Steven H.
sumber
Apakah lebih pendek untuk menempatkan setiap elemen dalam pasangan (angka, indeks), lalu mengurutkannya?
Nathan Merrill
Saya mencoba itu, tetapi itu memberi saya kebalikan dari daftar yang saya inginkan, dan sayangnya mendapatkan indeks dari suatu objek dalam daftar untuk membalikkannya sangat tidak efisien.
Steven H.
2

Ruby, 54 53 byte

Cobalah online

-1 byte dari memutakhirkan ke pendekatan @ Downgoat menggunakan hash untuk menyimpan nilai alih-alih menghitung duplikat setiap kali.

->a{b={};a.map{|e|a.sort.index(e)+b[e]=(b[e]||-1)+1}}
Nilai Tinta
sumber
Jenis Ruby tidak stabil , yang berarti bahwa ini mungkin melakukan hal yang salah pada ikatan.
Nathan Merrill
1
@NathaMerrill Itu bukan karena metode yang tepat saya gunakan untuk menghasilkan angka. Jika saya mengurutkan pada daftar indeks, itu akan menghasilkan hasil yang salah. Coba tautannya! Ini akan bekerja 60% dari waktu, setiap saat. Saya akan mengirim penjelasan nanti juga.
Nilai Tinta
Ah, baiklah. Saya tidak yakin apa yang dilakukan oleh sisa kode (saya tidak tahu Ruby)
Nathan Merrill
? Itu tidak melakukan hal yang salah pada ikatan, tetapi melakukan sesuatu yang salah 40% dari waktu?
WGroleau
@WGroleau ini adalah kutipan Anchorman. Kode saya berfungsi sepanjang waktu.
Nilai Tinta
2

Clojure, 83 byte

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

Saya membuat fungsi anonim yang menilai array input dan mengulanginya dua kali pada input. Panggilan pertama akan mengembalikan nilai. Panggilan kedua beroperasi pada tingkat dan mengembalikan peringkat.

mil
sumber
2

Brachylog , 27 byte

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

Cobalah online! atau verifikasi semua kasus uji .

Penjelasan

Ini adalah implementasi langsung dari hubungan berikut: setiap bilangan bulat dari output yang sesuai dengan elemen input adalah indeks elemen tersebut dalam input yang diurutkan.

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])
Fatalisasi
sumber
2

Mathematica, 15 byte

(o=Ordering)@*o
alephalpha
sumber
2

Mathematica, 135 byte

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

Common Lisp, 117 byte

(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))))

Terapkan transformasi Schwartzian dua kali.

;; 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)

Uji

(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
coredump
sumber
1

JavaScript (menggunakan perpustakaan eksternal) (105 byte)

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

Tautan ke lib: https://github.com/mvegh1/Enumerable Penjelasan kode: Buat metode anonim yang menerima daftar bilangan bulat. _.Dari menciptakan instance perpustakaan yang membungkus array dengan metode khusus. Pilih peta setiap item ke item baru, dengan mengambil alue "v", parsing ke string, lalu gabungkan "i" ndex dari item itu (ini memecahkan kasus nilai duplikat). Itu disimpan dalam variabel 'a'. Kemudian kami mengembalikan hasil dari yang berikut: Memetakan setiap item dalam 'a' ke indeks item dalam versi yang diurutkan dari (sebagai bilangan bulat), dan melemparkan kembali ke array JS asli

masukkan deskripsi gambar di sini

Perhatikan bahwa angka duplikat negatif tampaknya dicetak dalam urutan terbalik. Saya tidak yakin apakah itu membatalkan solusi ini? Secara teknis 8,10,4, -1, -1,8 harus 3,5,2,0,1,4 menurut OP tetapi kode saya mencetak 3,5,2,1,0,4 yang saya percaya adalah masih secara teknis valid?

applejacks01
sumber
1

GNU Core Utils, 39 33 byte

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

Menghasilkan output berbasis 1. Tambahkan -v0setelah yang keduanl untuk mendapatkan output berbasis 0. (+4 byte)

Perintah yang kami gunakan:

  • nl menambahkan nomor baris ke setiap baris input.
  • sort -n -k 2 urutkan berdasarkan kolom 2 secara numerik.
  • cut -f 1 mengambil kolom pertama yang dibatasi Tab, membuang sisanya.

Selain itu, -sopsi dapat diteruskan ke sortuntuk meminta jenis yang stabil, tetapi kami tidak membutuhkannya di sini. Jika dua item identik, sortakan menentukan urutannya dengan kembali ke kolom lain, yang dalam hal ini adalah output yang meningkat secara monoton nl. Jadi pengurutannya akan stabil tanpa perlu menentukannya, berdasarkan input.

joeytwiddle
sumber
1

Java 149 140 byte

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;
}

Golf

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;}

Terima kasih kepada @Kevin Cruissjen untuk cukur 9 byte.

Roman Gräf
sumber
@Nathan Merrill Saya perhatikan bahwa ketika saya bermain golf, tetapi lupa ketika saya menempelkan jawaban golf masuk
Roman Gräf
1
Anda bisa bermain golf lagi. Anda tidak perlu spasi di antara int[] adan int[] b. Anda dapat mengambil intkeluar dari loop. Dan karena Anda menggunakan b.lengthdua kali di awal Anda bisa meletakkannya di bidang yang terpisah. Jadi secara total seperti ini: 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 byte ) Hmm, juga, sepertinya tidak berfungsi .. Arrays.sort(...)tidak mengembalikan apa-apa (ini voidmetode), jadi bagaimana Anda dapat membandingkannya dengan b[i]...
Kevin Cruijssen
1

PHP, 88 byte

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

beroperasi pada argumen baris perintah; mencetak daftar yang diindeks, dipisahkan dengan garis bawah. Jalankan dengan -nr.

kerusakan

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
sumber
0

MATLAB, 29 byte

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

Sebagian besar bawaan sortir MATLAB akan mengembalikan array kedua opsional yang berisi indeks yang diurutkan. The j=bisa dihapus jika mencetak indeks diterima, daripada kembali mereka.

MattWH
sumber
0

CJam , 19 byte

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

Cobalah online!

Penjelasan:

_ 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
sumber