Anda harus menulis program atau fungsi yang mengurutkan daftar bersarang. Berikut adalah aturan untuk menyortir daftar bersarang:

Mari kita ambil daftar ini sebagai contoh:

((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Setiap elemen dalam daftar ini memiliki "prioritas". Elemen dihitung sebagai angka atau sublist. Pertama, dapatkan prioritas setiap elemen pada kedalaman yang sama. Jika suatu elemen hanyalah angka, prioritasnya sama dengan angka itu sendiri. Jika suatu elemen adalah sublist, prioritasnya adalah jumlah dari semua angka di dalamnya, tidak termasuk sub-sub daftar.

Jadi, prioritas semua elemen kedalaman 1 adalah:

 (  7 )  2  7  (    3       )  9
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

Urutkan setiap elemen berdasarkan prioritas. Jika ada dasi, Anda harus menjaga urutan yang sama dengan daftar aslinya.

 2  (     3      )  (  7 )  7  9
(2, (2, 1, (3, 4)), (5, 2), 7, 9) 

Ulangi untuk setiap sublist. Demikian pada sublist ini

(2, 1, (3, 4))

Prioritas kami terlihat seperti:

 2  1  (  7  )
(2, 1, (3, 4))

Jadi disortir, sepertinya:

(1, 2, (3, 4))

(3, 4)sudah diurutkan, jadi kita sudah selesai. Ulangi untuk (5, 2)yang menghasilkan (2, 5)dan kita selesai! Daftar terakhir kami adalah:

(2, (1, 2, (3, 4)), (2, 5), 7, 9) 

Aturan:

• Sangat meragukan, tetapi untuk berjaga-jaga jika Mathematica memiliki sesuatu untuk ini, tidak ada daftar sortir bawaan yang diizinkan. Fungsi menyortir biasa yang diperbolehkan.

• I / O dapat dalam format apa pun yang masuk akal.

• Setiap sublist akan berisi setidaknya satu nomor atau daftar. Juga, sublists dapat disarangkan beberapa level. Sebagai contoh, di (1, 2, (((3))))dalam (((3)))memiliki prioritas 0, karena hanya memiliki sublists di dalamnya.

• Daftar yang tidak valid (tanda kurung yang tidak cocok, non-angka, tipe braket yang salah, angka negatif, dll.) Menghasilkan perilaku yang tidak terdefinisi.

Tes I / O:

(1, 2, 3) ---> (1, 2, 3)

(1, 2, 6, 3, 9, 8) ---> (1, 2, 3, 6, 8, 9)

(4, 3, (2), (1)) ---> ((1), (2), 3, 4)

(4, 3, (2), ((1))) ---> (((1)), (2), 3, 4)

(5, (1, 2, (9, 8))) ---> ((1, 2, (8, 9)), 5)

(3, (1, 2), (2, 1)) ---> (3, (1, 2), (1, 2))

(3, (1, 2, (99)), (2, 1, (34))) ---> (3, (1, 2, (99)), (1, 2, (34)))

(7, 2, (1, (9, 12)), (4, 3, 2, (1, 2))) ---> ((1, (9, 12)), 2, 7, (2, 3, (1, 2), 4))

Jawaban terpendek dalam byte menang.

Jelly, 13 byte

fFSµ€Ụị߀µ¹<?

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

fFSµ€Ụị߀µ¹<?  Main link. Input: A (list)

   µ€          Apply the chain to the left to each item B in A.
 F             Flatten B.
f              Filter; intersect B with flattened B, yielding a list.
               This returns the numbers in B if B is a list, [B] if B is a number.
  S            Compute the sum of the resulting list.
     Ụ         Sort the indices of A according to the computed sums.
       ߀      Recursively apply the main link to each B in A.
      ị        Retrieve the items of the list (right) at those indices (left).
         µ     Convert the preceding chain into a single link.
            ?  If:
           <     A compared with itself is truthy:
                   Execute the link to the left.
          ¹      Else, apply the identity function to A.

Membandingkan ( <) angka dengan dirinya sendiri menghasilkan 0 (falsy), tetapi membandingkan daftar yang tidak kosong dengan dirinya sendiri menghasilkan daftar 0 (benar), sehingga <dapat digunakan untuk membedakan angka dari daftar.

Python 2, 114 101 78 73 62 byte

k=lambda t:t*(t<[])or t.sort(key=k)or sum(z for z in t if[]>z)

Saya tahu ada cara yang lebih baik untuk menyaring daftar.

Mengurutkan daftar python (dan sublistinya) di tempat.

https://eval.in/540457 terima kasih @tac karena memberi tahu saya bahwa solusi di tempat dapat diterima, dan @xnor + @feersum untuk optimasi lebih lanjut!

Lua, 172 byte

function p(a)if type(a)~="table"then return a end s(a)local t=0 for i,v in next,a do t=t+p(v)end return t end
function s(t)table.sort(t,function(a,b)return p(a)<p(b)end)end

Fungsi smengurutkan tabel Lua (struktur data yang berfungsi sebagai daftar di antara hal-hal lain di Lua) di tempat sesuai dengan aturan.

Mathematica, 50 byte

#0/@SortBy[#,Tr@Cases[#,_Integer,{0,1}]&]~Check~#&

Metode rekursif sederhana yang digunakan SortBy. Abaikan pesannya.

Haskell, 160 151 135 byte

import Data.List
data T=N Int|T[T]deriving Show
p(N x)=x
p(T t)=sum$[x|N x<-t]
f(N x)=N x
f(T t)=T$sortBy((.p).compare.p)$map f$t

Masalah pertama adalah daftar bersarang. Haskell mensyaratkan bahwa semua elemen daftar memiliki tipe yang sama; khususnya, bilangan bulat dan daftar bilangan bulat tidak bertipe sama. Dengan kata lain, daftar bersarang variabel bukanlah daftar, itu adalah pohon mawar!

Jadi pertama-tama, kita harus mendefinisikan tipe data untuk pohon mawar:

data T = N Int | T [T]

(Strictly, deriving Showhanya diperlukan jika Anda ingin melihat hasil. Tapi itu masalah teknis.) Dengan definisi ini di tempat, kita dapat menulis daftar seperti (1, 2, (3, 4))sebagai

T [N 1, N 2, T [N 3, N 4]]

yang jauh lebih mudah dibaca. Tapi apa pun; itu adalah terjemahan mekanis yang sepele. Awali setiap angka dengan Ndan setiap subtree dengan T.

Sekarang kita perlu menghitung prioritas. Ini akan mudah jika prioritas subtree adalah jumlah sederhana semua elemen yang dikandungnya. Itu akan menjadi loop rekursif sepele. Tetapi karena tidak, kita perlu mendefinisikan dua fungsi: satu yang berulang, dan yang lain tidak.

p (N x) = x
p (T t) = sum $ map q t

q (N x) = x
q _     = 0

Jika kita menjumlahkan semua subelemen, maka qtidak perlu ada, menyimpan sejumlah besar karakter. Baiklah!

Edit: Sebenarnya, beberapa komentator menunjukkan bahwa Anda dapat menghindari qmenggunakan pemahaman daftar: [ x | N x <- t]. Panggilan bagus, kawan!

(Pada kenyataannya, ptidak perlu ada juga; kita dapat membuat kompiler menghasilkan otomatis sebuah Ordcontoh untuk kita dalam beberapa karakter, dan implementasi default ini akan cocok dengan spek.)

Akhirnya, kita perlu rekursif atas semua sub-pohon dan mengurutkannya:

f (N x) = N x
f (T t) = T $ sortBy (\ x y -> compare (p x) (p y)) $ map f $ t

Yaitu, fmengurutkan pohon dengan secara rekursif menerapkan sendiri ke semua elemen ( map f), dan kemudian memanggil sortByfungsi untuk mengurutkan tingkat atas. Baris pertama mengatakan bahwa menyortir angka tidak melakukan apa-apa, dan perlu untuk mengakhiri rekursi.

CLISP, 380 byte

(defun q(L)(if(null L)L(append(append(q(car(s(cdr L)(car L))))(list(car L)))(q(cadr(s(cdr L)(car L))))))))(defun s(L E)(if(not(atom(car L)))(setq L(cons(q(car L))(cdr L))))(cond((null L)'(nil nil))((<(v(car L))E)(list(cons(car L)(car(s(cdr L)E)))(cadr(s(cdr L)E))))(T(list(car(s(cdr L)E))(cons(car L)(cadr(s(cdr L)E)))))))(defun v(L)(if(atom L)L(apply'+(remove-if-not #'atom L))))

Panggil fungsi q dengan daftar.

Saya seorang pemula, tolong jangan bunuh saya ^^

Pyth, 15 byte

L?sIbbossI#NyMb

Suite uji

Fungsi rekursif, yang berfungsi sebagai berikut:

L?sIbbossI#NyMb
L                  define y(b):
 ?sIb              If b is an integer:          (invariant under the s function)
     b             Return it.
            yMb    Else, apply y recursively to all of the elements of b,
      o            Then sort b by
        sI#N       For each element, the elements of that list that are integers.
                   This is luckily a nop on integers.
       s           Summed.

Java, 219 byte

import java.util.*;List f(List l){l.sort(Comparator.comparing(o->{if(o instanceof Integer)return(Integer)o;f((List)o);return((List) o).stream().filter(i->i instanceof Integer).mapToInt(i->(Integer)i).sum();}));return l;}

Dengan jeda baris:

import java.util.*;
List f(List l){
    l.sort(Comparator.comparing(o -> {
        if (o instanceof Integer)
            return (Integer) o;
        f((List) o);
        return ((List) o).stream().filter(i -> i instanceof Integer).mapToInt(i -> (Integer) i).sum();
    }));
    return l;
}

Ada banyak casting yang benar-benar menghitung jumlah byte. : P

Nilai integer dimasukkan ke dalam Comparator, dan daftar bersarang diurutkan terlebih dahulu sebelum jumlah hanya nilai integer yang diberikan kepada Comparator. Nilai-nilai ini adalah bagaimana Pembanding menentukan posisi mereka di dalam daftar ketika diurutkan.

Coba di sini .

JavaScript (ES6), 86 byte

f=a=>a.map?a.map(f).sort((a,b)=>p(a)-p(b),p=a=>a.map?a.map(a=>t+=a.map?0:a,t=0)|t:a):a

Semua itu memeriksa array :-(