Musisz napisać program lub funkcję sortującą listę zagnieżdżoną. Oto zasady sortowania listy zagnieżdżonej:

Weźmy tę listę jako przykład:

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

Każdy element na tej liście ma „priorytet”. Element liczy się jako liczba lub lista podrzędna. Najpierw uzyskaj priorytet każdego elementu na tej samej głębokości. Jeśli element jest tylko liczbą, jego priorytet jest taki sam jak sama liczba. Jeśli element jest podlistą, jego priorytetem jest suma wszystkich zawartych w nim liczb , nie uwzględniając żadnych podlist.

Zatem priorytetami wszystkich elementów głębokości 1 są:

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

Posortuj każdy element według priorytetu. W przypadku remisu musisz zachować tę samą kolejność, co oryginalną listę.

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

Powtórz dla każdej podlisty. Więc na tej liście

(2, 1, (3, 4))

Nasze priorytety wyglądają następująco:

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

Tak posortowane, wygląda następująco:

(1, 2, (3, 4))

(3, 4)jest już posortowane, więc skończyliśmy. Powtórz dla (5, 2)których wyniki (2, 5)i gotowe! Nasza ostateczna lista to:

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

Zasady:

• Bardzo wątpliwe, ale na wszelki wypadek, gdy Mathematica ma coś do tego, żadne wbudowane sortowanie listy zagnieżdżonej nie jest dozwolone. Dozwolone są regularne funkcje sortowania .

• I / O może mieć dowolny rozsądny format.

• Każda lista podrzędna będzie zawierać co najmniej jeden numer lub listę. Podlisty można również zagnieżdżać na kilku poziomach. Na przykład w (1, 2, (((3))))elemencie (((3)))ma priorytet 0, ponieważ ma w nim tylko listy podrzędne.

• Nieprawidłowe listy (niedopasowane nawiasy, niepoliczalne liczby, niewłaściwe typy nawiasów, liczby ujemne itp.) Powodują niezdefiniowane zachowanie.

Test we / wy:

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

Najkrótsza odpowiedź w bajtach wygrywa.

Galaretka, 13 bajtów

fFSµ€Ụị߀µ¹<?

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

Jak to działa

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.

Porównanie ( <) liczby w sobie daje 0 (falsy), lecz w porównaniu niepusty listę ze sobą uzyskuje listę 0 „s (truthy), a więc <mogą być używane do rozróżniania numerów z listy.

Python 2, 114 101 78 73 62 bajtów

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

Wiedziałem , że istnieje lepszy sposób na odfiltrowanie list.

Sortuje listę python (i jej listy podrzędne) w miejscu.

https://eval.in/540457 dzięki @tac za poinformowanie mnie, że rozwiązania na miejscu są dopuszczalne, a @xnor + @feersum za dalsze optymalizacje!

Lua, 172 bajty

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

Funkcja ssortuje tabelę Lua (strukturę danych, która służy jako lista między innymi w Lua) zgodnie z regułami.

Mathematica, 50 bajtów

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

Prosta metoda rekurencyjna, która wykorzystuje SortBy. Zignoruj ​​wiadomości.

Haskell, 160 151 135 bajtów

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

Pierwszym problemem są listy zagnieżdżone. Haskell wymaga, aby wszystkie elementy listy miały ten sam typ; w szczególności liczba całkowita i lista liczb całkowitych nie są tego samego typu. Innymi słowy, lista zagnieżdżona w zmiennej nie jest listą, to drzewo różane!

Najpierw musimy zdefiniować typ danych dla drzew róży:

data T = N Int | T [T]

(Ściśle rzecz biorąc, deriving Showjest to konieczne tylko, jeśli chcesz zobaczyć wyniki. Ale to jest kwestia techniczna.) Po wprowadzeniu tej definicji możemy napisać listę taką (1, 2, (3, 4))jak:

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

co jest znacznie mniej czytelne. Ale cokolwiek; to banalne, mechaniczne tłumaczenie. Poprzedź każdą cyfrę Ni każde poddrzewo znakiem T.

Teraz musimy obliczyć priorytety. Byłoby to łatwe, gdyby priorytetem poddrzewa była prosta suma wszystkich zawartych w nim elementów. To byłaby trywialna pętla rekurencyjna. Ale ponieważ tak nie jest, musimy zdefiniować dwie funkcje: jedną, która się powtarza, i jedną, która nie powtarza się.

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

q (N x) = x
q _     = 0

Gdybyśmy zsumowali wszystkie podelementy, qnie musielibyśmy istnieć, oszczędzając ogromną liczbę znaków. No cóż!

Edycja: Faktycznie, kilka commentors podkreślić, że można uniknąć qstosując listowych: [ x | N x <- t]. Dobra rozmowa!

(W rzeczywistości też pnie musiałby istnieć; moglibyśmy mieć kompilator automatycznie generujący Orddla nas instancję w kilku znakach, a ta domyślna implementacja byłaby zgodna ze specyfikacją.)

Wreszcie musimy rekurencyjnie wykonywać wszystkie pod-drzewa i sortować je:

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

Oznacza to, że fsortuje drzewo poprzez rekurencyjne zastosowanie się do wszystkich elementów ( map f), a następnie wywołanie sortByfunkcji w celu posortowania najwyższego poziomu. Pierwszy wiersz mówi, że sortowanie liczb nic nie robi i jest konieczne, aby zakończyć rekurencję.

CLISP, 380 bajtów

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

Wywołaj funkcję q z listą.

Jestem seplenieniem, proszę, nie zabijaj mnie ^^

Pyth, 15 bajtów

L?sIbbossI#NyMb

Zestaw testowy

Funkcja rekurencyjna, która działa w następujący sposób:

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 bajtów

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

Z podziałami linii:

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

Jest dużo castingu, który naprawdę podnosi liczbę bajtów. : P

Wartości całkowite są wprowadzane do Komparatora, a zagnieżdżone listy są sortowane najpierw, zanim suma samych wartości całkowitych zostanie podana do Komparatora. Te wartości określają, w jaki sposób Komparator określa swoją pozycję na liście podczas sortowania.

Wypróbuj tutaj .

JavaScript (ES6), 86 bajtów

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

Całe sprawdzanie tablicy :-(