Tukar indeks dan nilai

29

Tugas

Tulis program atau fungsi yang inputnya adalah daftar / larik X bilangan bulat, dan yang keluarannya adalah daftar himpunan bilangan bulat Y , sedemikian rupa sehingga untuk setiap elemen e dalam setiap set Y [ i ], X [ e ] = i , dan sehingga jumlah elemen dalam set di Y sama dengan jumlah elemen dalam X .

(Ini pada dasarnya operasi yang sama dengan membalik hashtable / kamus, kecuali diterapkan pada array sebagai gantinya.)

Contohnya

Contoh-contoh ini mengasumsikan pengindeksan berbasis 1, tetapi Anda dapat menggunakan pengindeksan berbasis 0 jika Anda mau.

X             Y
[4]           [{},{},{},{1}]
[1,2,3]       [{1},{2},{3}]
[2,2,2]       [{},{1,2,3}]
[5,5,6,6]     [{},{},{},{},{1,2},{3,4}]
[6,6,5,5]     [{},{},{},{},{3,4},{1,2}]

Klarifikasi

  • Anda dapat mewakili satu set sebagai daftar, jika diinginkan. Jika Anda melakukannya, urutan elemen-elemennya tidak masalah, tetapi Anda mungkin tidak mengulangi elemen-elemen itu.
  • Anda dapat menggunakan format I / O yang tidak ambigu; misalnya, Anda dapat memisahkan elemen dari himpunan dengan spasi, dan himpunan itu sendiri dengan baris baru.
  • Y harus panjang, dan setidaknya cukup lama untuk memiliki semua elemen X sebagai indeks array. Namun, mungkin lebih lama dari elemen maksimal X (elemen tambahan akan menjadi set kosong).
  • Elemen X semua akan menjadi indeks array yang valid, yaitu bilangan bulat non-negatif jika Anda menggunakan pengindeksan berbasis 0, atau bilangan bulat positif jika Anda menggunakan pengindeksan berbasis 1.

Kondisi kemenangan

Sebagai tantangan , lebih pendek lebih baik.

Cyoce
sumber
Terkait . Di pos Sandbox (sekarang dihapus, tetapi Anda dapat melihatnya jika Anda memiliki reputasi), kami memutuskan itu mungkin bukan duplikat, tetapi jangan ragu untuk memilih untuk menutup jika Anda tidak setuju.
Apakah "urutan elemen-elemennya tidak penting" berarti bahwa output dari [5,5,6,6]dan [6,6,5,5]dapat identik?
Leaky Nun
1
@ LeakyNun Urutan elemen set di daftar output tidak masalah. Jadi [5,5,6,6]dan [6,6,5,5]tidak dapat memiliki output yang identik, tetapi output untuk [5,5,6,6]bisa juga bisa, mis [{},{},{},{},{2,1},{4,3}].
ngenisis
Apakah ada nilai maksimal asumsi dari indeks dalam X? Juga dapat set kosong memiliki 0 di dalamnya bukannya benar-benar kosong? Misalnya apakah [{0},{0},{0},{0},{1,2},{3,4}]output yang valid untuk [5,5,6,6]?
Skidsdev
@ Mayube: Tidak untuk jawaban pertama (meskipun jika Anda menggunakan bahasa yang memiliki rentang terbatas pada bilangan bulat, Anda dapat menulis program seolah-olah bilangan bulat bisa besar tanpa batas, dan tidak khawatir tentang hal itu melanggar jika seseorang memberi Anda out- of-range integer sebagai input). Sehubungan dengan pertanyaan kedua, itu adalah sintaks yang tidak ambigu (jika aneh) ketika Anda menggunakan pengindeksan berbasis 1, jadi ya dalam kasus itu (jelas, tidak jika Anda menggunakan pengindeksan berbasis 0 karena 0 akan berarti sesuatu lain.)

Jawaban:

9

MATL , 8 byte

tn:IXQ&D

Input adalah vektor kolom, dengan ;sebagai pemisah (misalnya [2;2;2]). Output adalah representasi string dari array sel vektor baris (misalnya {[]; [1 2 3]}). Vektor baris elemen tunggal sama dengan angka (jadi {1; 2; 3}akan menjadi output bukan {[1]; [2]; [3]}).

Cobalah online! Atau verifikasi semua kasus uji .

Penjelasan

t     % Implicit input, say x. Duplicate
n     % Number of elements, say N
:     % Range: [1 2 ... N]
IXQ   % accumarray(x, [1 2 ... N], [], @(x){sort(x).'})
&D    % String representation

Sebagian besar pekerjaan dilakukan oleh fungsi orde tinggi Matlab accumarray, yang mengelompokkan elemen dalam input kedua sesuai dengan nilai yang cocok di yang pertama, dan menerapkan fungsi yang ditentukan untuk setiap grup. Fungsi dalam kasus ini adalah @(x){sort(x).'}, yang menampilkan elemen yang diurutkan dalam setiap grup dan menyebabkan hasil untuk semua grup dikemas dalam array sel.

Luis Mendo
sumber
7

Python, 69 byte

lambda s:[[j for j,x in enumerate(s)if x==i]for i in range(max(s)+1)]

Menggunakan pengindeksan berbasis 0.

Uriel
sumber
7

Jelly , 7 5 byte

=þṀT€

Cobalah online!

Bagaimana itu bekerja

=þṀT€  Main link. Argument: A (array)

  Ṁ    Yield m, the maximum of A.
=þ     Equals table; for each t in [1, ..., m], compare all elemnts of A with t,
       yielding a 2D Boolean array.
   T€  Truth each; for each Boolean array, yield all indices of 1.
Dennis
sumber
5

Jelly , 8 byte

Jẋ"Ṭ€;"/

Cobalah online!

Bagaimana itu bekerja

Jẋ"Ṭ€;"/  argument: z           eg. [6,6,4,4]
J         [1 .. len(z)]             [1,2,3,4]
   Ṭ€     untruth each of z         [[0,0,0,0,0,1],
                                     [0,0,0,0,0,1],
                                     [0,0,0,1],
                                     [0,0,0,1]]
 ẋ"       repeat each of ^^         [[[],[],[],[],[],[1]],
          as many times as           [[],[],[],[],[],[2]],
          each of ^                  [[],[],[],[3]],
                                     [[],[],[],[4]]]
       /  reduce by...
     ;"   vectorized concatenation  [[],[],[],[3,4],[],[1,2]]
Biarawati Bocor
sumber
4

Mathematica, 36 byte

Join@@@#~Position~n~Table~{n,Max@#}&

Penjelasan

masukkan deskripsi gambar di sini

Untuk masing-masing ndalam {1, 2, ..., Max@#}, di mana Max@#bilangan bulat terbesar dalam daftar input, menghitung Positions di mana nmuncul dalam daftar input #. Karena Position[{6,6,5,5},5](misalnya) kembali {{3},{4}}, kami kemudian Apply Joinke semua elemen di tingkat {1}hasil.

ngenisis
sumber
3

Haskell , 45 byte

smengambil daftar bilangan bulat dan mengembalikan daftar daftar. 1-diindeks untuk menjaga agar input test case tidak dimodifikasi (walaupun output mendapatkan beberapa daftar kosong tambahan).

s l=[[i|(i,y)<-zip[1..]l,y==x]|x<-[1..sum l]]

Cobalah online!

Ini adalah daftar pemahaman bersarang cukup mudah. Satu-satunya perubahan kecil adalah mengambil keuntungan dari opsi untuk membuat daftar yang lebih panjang dengan menggunakan sumalih-alih maximum.

Ørjan Johansen
sumber
3

PHP, 55 byte

<?while($i<=max($_GET))print_r(array_keys($_GET,$i++));

Diindeks 0.

pengguna63956
sumber
3

R, 68 49 47 byte

lapply(1:max(x<-scan()),function(y)which(y==x)) 

Anehnya, jauh lebih mudah daripada solusi yang lebih lama. Mengambil vektor xdari STDIN, membuat vektor dari 1hingga max(x), secara implisit menghasilkan daftar panjang max(x), dan memeriksa indeks mana yang xsesuai dengan yang ada dalam daftar baru. Secara implisit mencetak output.

Versi yang lebih lama:

o=vector('list',max(x<-scan()));for(i in x)o[[i]]=c(o[[i]],F<-F+1);o

Pendekatan yang sedikit berbeda dengan jawaban R lainnya. Membawa vektor ke STDIN, membuat daftar dengan panjang yang sama dengan nilai maksimum dalam input. Lewati input dan tambahkan indeks ke tempat yang tepat.

Menggunakan pengindeksan berbasis 1.

JAD
sumber
2

Python 2 , 91 86 85 byte

Saya pemrograman pada ponsel saya, tetapi saya sangat menyukai tantangan ini. Saya pasti bisa bermain golf lebih jauh.

def f(a):
 r=[[]for i in range(max(a)+1)]
 for i,j in enumerate(a):r[j]+=[i]
 print r

Cobalah online!

benar-benar manusiawi
sumber
Bermain golf lagi dengan pemahaman daftar bersarang. : D
totallyhuman
2

Jelly , 9 byte

Ṭ+\ịĠȧ@"Ṭ

1-diindeks, set kosong diwakili 0, set satu item diwakili sebagai Nset beberapa item diwakili[M,N,...]

Cobalah online!

Bagaimana?

Ṭ+\ịĠȧ@"Ṭ - Main link: list a        e.g. [6,6,4,4]
Ṭ         - untruth a                     [0,0,0,1,0,1]
  \       - cumulative reduce with:
 +        -   addition                    [0,0,0,1,1,2]
    Ġ     - group indices of a by value   [[3,4],[1,2]]
   ị      - index into                    [[1,2],[1,2],[1,2],[3,4],[3,4],[1,2]]
        Ṭ - untruth a                     [0,0,0,1,0,1]
       "  - zip with:
     ȧ@   -   and with reversed @rguments [0,0,0,[3,4],0,[1,2]]
Jonathan Allan
sumber
2

JavaScript (ES6), 64 62 byte

Disimpan 2 byte berkat @SteveBennett


Mengambil input yang diindeks 0. Mengembalikan daftar set yang dipisahkan koma.

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&`{${o.join`},{`}}`

Uji kasus


Versi alternatif, 53 byte

Jika output yang disederhanakan seperti '||||3,2|1,0'dapat diterima, kita bisa melakukan:

a=>a.map((n,i)=>o[n]=[i,...o[n]||[]],o=[])&&o.join`|`
Arnauld
sumber
Wow. Saya sangat bingung bagaimana `{${o.join`},{`}}`ES2015 legal.
Steve Bennett
@SteveBennett, ini adalah templat literal . Dalam versi JS yang lebih lama "{" + o.join("},{") + "}", jika itu membuatnya lebih jelas.
Shaggy
Tidak, saya tahu tentang itu - itu adalah tanda kutip setelah kata join yang membingungkan saya. Apakah itu menutup string (dalam hal ini wtf) atau apakah itu bagaimana Anda melarikan diri dari penjepit dekat?
Steve Bennett
Hmm, ok, jadi dalam konteks join`ini setara dengan join('. Tidak tahu Anda bisa melakukan itu.
Steve Bennett
Ah, sekarang saya mengerti. Ini literal templat yang ditandai. Yang Anda dapat menyalahgunakan untuk menyimpan beberapa karakter setiap kali memanggil fungsi yang mengambil satu argumen string (dan mengabaikan orang lain): array.join` `. Sangat membingungkan di sini karena Anda menyematkannya ke dalam string template, dan bahkan lebih membingungkan, string yang bergabung adalah },{, yang secara kebetulan tampak seperti bagian dari string template ... dan tetap saja aneh dan jelek pula. :)
Steve Bennett
1

Bash , 109 byte

Sayang sekali tidak ada built-in untuk nilai max array.

a=($@)
for((x=m=1;x<=m;x++)){ for((y=0;y<$#;)){((m<a[y]))&&((m=a[y]));((a[y++]==x))&&printf "%d " $y;};echo;}

Cobalah online!

Maxim Mikhaylov
sumber
1

Mathematica 62 byte

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&

Saya akan menjalankannya untuk Anda

(Y={}~Table~Max@#;Y[[#[[j]]]]~AppendTo~j~Table~{j,Tr[1^#]};Y)&[{4,5,2,3,3,8,6,3}]

{{}, {3}, {4, 5, 8}, {1}, {2}, {7}, {}, {6}}

Cobalah online (cukup tempel kode dengan ctrl-v dan tekan shift + enter)
jangan lupa untuk menempelkan daftar input di akhir seperti pada contoh di atas

J42161217
sumber
Selamat datang di PPCG! Anda dapat menyimpan byte dengan menggunakan notasi infix untuk AppendTo. Juga, {j,1,Length[#1]}bisa saja {j,Length@#}, atau bahkan lebih pendek {j,Tr[1^#]},. Tr[1^#]adalah trik yang cukup umum untuk menghemat byte dari penggunaan Length.
ngenisis
1

Perl 6 ,  36 32  29 byte

->\a{map {a.grep(*==$_):k},1..a.max}

Cobalah

{map {.grep(*==$^a):k},1.. .max}

Cobalah

{map {.grep($^a):k},1.. .max}

Cobalah


Diperluas:

{  # bare block lambda with implicit parameter 「$_」

  map

    {  # bare block lambda with placeholder parameter 「$a」

      .grep(  # grep for the values in 「$_」
        $^a   # that are equal to the currently tested value (and declare param)
      ) :k    # return the key (index) rather than the value
    },

    1 .. .max # Range from 1 to the maximum value in 「$_」

}

Mengembalikan indeks berbasis nol, untuk mendapatkan 1 menggunakan lintas operator ( X) dikombinasikan dengan +op . (33 byte)

{1 X+.grep($^a):k}

Untuk mendapatkannya kembali Set s cukup tambahkanset di sana (total 37 byte)

{set 1 X+.grep($^a):k}
Brad Gilbert b2gills
sumber
1

R, 80 72 byte

1-diindeks, diambil Xdari stdin. Mengembalikan daftar vektor indeks, dengan NULLsebagai set kosong.

X=scan();Y=vector('list',max(X));Y[X]=lapply(X,function(x)which(X==x));Y

Cobalah online!

versi lama:

X=scan();Y=vector('list',max(X));for(i in 1:length(X))Y[[X[i]]]=c(Y[[X[i]]],i);Y

Cobalah online!

Giuseppe
sumber
Saya pikir itu Y=list();bekerja dengan baik
rturnbull
Berhasil mencukur fewbyte dalam jawaban saya :) codegolf.stackexchange.com/a/120024/59530
JAD
0

Röda , 51 byte

f s{seq(1,max(s))|[[s()|enum|[_2+1]if[_1=i]]]for i}

Ini adalah port dari jawaban Python oleh Uriel .

Versi lain (88 byte):

f a{I=indexOf;seq(1,max(a))|{|i|b=a[:]c=[]x=1{c+=x+I(i,b)b-=i;x++}until[I(i,b)<0];[c]}_}

Cobalah online!

Keduanya 1-diindeks.

fergusq
sumber
0

PowerShell, 81 byte

$args[0]|%{if($_-gt($c=$r.count)){$r+=@($t)*($_-$c)}$r[--$_]+=,++$i};$r|%{"{$_}"}

Cobalah online!

1-diindeks.

Andrei Odegov
sumber
0

GNU Make , 214 213 208 204 byte

X=$(MAKECMDGOALS)
M=0
P=$(eval N=$(word $1,$X))$(if $N,$(if $(shell dc -e$Nd$Mds.\>.p),$(eval M=$N),)$(eval A$N+=$1$(call $0,$(shell expr $1 + 1))),)
$(call P,1)$(foreach K,$(shell seq $M),$(info $(A$K)))

I / O: input array melalui argumen, output ke stdout, satu per baris, dipisahkan oleh spasi.

$ make -f swap.mk 2 2 2

3 2 1
make: *** No rule to make target `2'.  Stop.

Penjelasan

X=$(MAKECMDGOALS)     # Input array
M=0                   # Max value encountered in X
P=$(eval
    N=$(word $1,$X))  # Get next word from X
  $(if $N,$(if $(shell dc -e$Nd$Mds.\>.p),
    $(eval M=$N),)    # Update M
    $(eval A$N+=$1    # Append index to a variable named after value
      $(call $0,      # Recurse (call returns empty string)
        $(shell expr $1 + 1))),)
$(call P,1)           # Initial call to P. 1 is the first index
$(foreach K,          # Print all values of A* variables
  $(shell seq $M),
  $(info $(A$K)))     # Uninitialized ones default to empty strings

Urutan indeks dalam set dibalik karena Ppanggilan itu sendiri secara rekursif sebelum memperbarui A$2(panggilan dieksekusi dalam evaluasi sisi kanan).

eush77
sumber
Apakah makeada cara untuk melakukan aritmatika itu sendiri? Memanggil ke dalam program eksternal untuk melakukannya rasanya seperti curang, karena Anda mungkin bisa memasukkan lebih banyak algoritma ke dalam program-program itu dan berakhir dengan program yang lebih pendek.
@ ais523 Tidak. Versi sebelumnya digunakan bcdan grep. Saya juga bisa menggunakan testdan $?. dcmemiliki sintaks terser, tetapi terus terang semua ini merasakan hal yang sama.
eush77
0

Gangguan Umum, 91 byte

(lambda(x &aux(l(make-list(eval`(max,@x))))(i 0))(dolist(y x l)(push(incf i)(nth(1- y)l))))

Pengindeksan berbasis 1, mengembalikan set sebagai daftar.

Cobalah online!

Renzo
sumber
0

k , 13 byte

{(=x)@!1+|/x}

Ini diindeks 0.

Cobalah online!

{           } /function(x)
 (=x)         /make a map/dictionary of values to their indices
         |/x  /get maximum value in x
      !1+     /make a range from 0 to the value, inclusive
     @        /get map value at each of the values in the range
              /    0N is given where there is no result
zgrep
sumber