Sie müssen ein Programm oder eine Funktion schreiben, die eine verschachtelte Liste sortiert. Hier sind die Regeln zum Sortieren einer verschachtelten Liste:

Nehmen wir diese Liste als Beispiel:

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

Jedes Element in dieser Liste hat eine "Priorität". Ein Element zählt als Zahl oder als Unterliste. Holen Sie sich zunächst die Priorität jedes Elements in der gleichen Tiefe. Wenn ein Element nur eine Zahl ist, entspricht seine Priorität der Zahl selbst. Wenn ein Element eine Unterliste ist, ist seine Priorität die Summe aller darin enthaltenen Zahlen , ohne Unterlisten.

Die Prioritäten aller Elemente von Tiefe 1 lauten also:

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

Sortieren Sie jedes Element nach Priorität. Bei Stimmengleichheit müssen Sie die Reihenfolge der ursprünglichen Liste beibehalten.

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

Wiederholen Sie dies für jede Unterliste. Also auf dieser Unterliste

(2, 1, (3, 4))

Unsere Prioritäten sehen so aus:

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

So sortiert sieht es aus:

(1, 2, (3, 4))

(3, 4)ist schon sortiert, also sind wir fertig. Wiederholen Sie für (5, 2)welche Ergebnisse (2, 5)und wir sind fertig! Unsere endgültige Liste ist:

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

Regeln:

• Sehr zweifelhaft, aber für den Fall, dass Mathematica etwas dafür hat, sind keine eingebauten Sortierfunktionen für verschachtelte Listen zulässig. Reguläre Sortierfunktionen sind erlaubt.

• I / O kann in jedem vernünftigen Format vorliegen.

• Jede Unterliste enthält mindestens eine Nummer oder Liste. Unterlisten können auch mehrere Ebenen tief verschachtelt werden. Zum Beispiel in (1, 2, (((3))))der (((3)))hat eine Priorität von 0, da es nur Teil - Listen in ihm hat.

• Ungültige Listen (nicht übereinstimmende Klammern, Nicht-Zahlen, falsche Klammertypen, negative Zahlen usw.) führen zu undefiniertem Verhalten.

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

Kürzeste Antwort in Bytes gewinnt.

Jelly, 13 Bytes

fFSµ€Ụị߀µ¹<?

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

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.

Wenn Sie ( <) eine Zahl mit sich selbst vergleichen, erhalten Sie 0 (falsch), aber wenn Sie eine nicht leere Liste mit sich selbst vergleichen, erhalten Sie eine Liste mit 0 (wahr). Sie <können also verwendet werden, um Zahlen von Listen zu unterscheiden.

Python 2, 114 101 78 73 62 Bytes

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

Ich wusste, dass es eine bessere Möglichkeit gibt, Listen herauszufiltern.

Sortiert eine Python-Liste (und ihre Unterlisten) an Ort und Stelle.

https://eval.in/540457 danke @tac für die Benachrichtigung, dass In-Place-Lösungen akzeptabel sind, und @xnor + @feersum für weitere Optimierungen!

Lua, 172 Bytes

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

Die Funktion ssortiert eine Lua-Tabelle (eine Datenstruktur, die unter anderem in Lua als Liste dient) nach den Regeln.

Mathematica, 50 Bytes

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

Einfache rekursive Methode, die verwendet SortBy. Ignoriere die Nachrichten.

Haskell, 160 151 135 Bytes

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

Das erste Problem sind verschachtelte Listen. Haskell setzt voraus, dass alle Elemente einer Liste denselben Typ haben. Insbesondere sind eine Ganzzahl und eine Liste von Ganzzahlen nicht vom selben Typ. Mit anderen Worten, eine Liste mit verschachtelten Variablen ist keine Liste, sondern ein Rosenbaum!

Also müssen wir zuerst einen Datentyp für Rosenbäume definieren:

data T = N Int | T [T]

(Streng genommen deriving Showist nur erforderlich , wenn Sie wollen sehen , die Ergebnisse. Aber das ist eine Form .) Mit dieser Definition vorhanden ist , können wir eine Liste schreiben, wie (1, 2, (3, 4))als

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

das ist deutlich weniger lesbar. Aber was auch immer; Es ist eine triviale, maschinelle Übersetzung. Stellen Sie jeder Zahl Nund jedem Teilbaum Folgendes voran T.

Jetzt müssen wir Prioritäten berechnen. Dies wäre einfach, wenn die Priorität eines Teilbaums einfach die Summe aller darin enthaltenen Elemente wäre. Das wäre eine triviale rekursive Schleife. Da dies jedoch nicht der Fall ist, müssen wir zwei Funktionen definieren : eine, die rekursiv ist, und eine, die nicht rekursiv ist.

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

q (N x) = x
q _     = 0

Wenn wir alle Unterelemente summieren qwürden , müssten wir nicht existieren und eine große Anzahl von Zeichen speichern. Naja!

Edit: Eigentlich mehrere commentors weisen darauf hin , dass Sie vermeiden können , qeine Liste Verständnis mit: [ x | N x <- t]. Guter Anruf, Leute!

(Eigentlich pmüsste es auch nicht existieren. Der Compiler könnte Ordin wenigen Zeichen automatisch eine Instanz für uns generieren , und diese Standardimplementierung würde der Spezifikation entsprechen.)

Schließlich müssen wir über alle Unterbäume rekursiv arbeiten und sie sortieren:

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

Das heißt, fsortiert ein Baum rekursiv sich auf alle Elemente anwenden ( map f) und dann den Aufruf der sortByFunktion der obersten Ebene zu sortieren. Die erste Zeile besagt, dass das Sortieren einer Zahl nichts bewirkt und notwendig ist, um die Rekursion zu beenden.

CLISP, 380 Bytes

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

Rufen Sie die Funktion q mit einer Liste auf.

Ich bin ein Idiot, bitte töte mich nicht ^^

Pyth, 15 Bytes

L?sIbbossI#NyMb

Testsuite

Eine rekursive Funktion, die wie folgt funktioniert:

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 Bytes

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

Mit Zeilenumbrüchen:

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

Es wird viel gewirkt, was die Anzahl der Bytes wirklich erhöht. : P

Ganzzahlige Werte werden in einen Komparator eingespeist, und verschachtelte Listen werden zuerst sortiert, bevor dem Komparator nur die Summe der ganzzahligen Werte übergeben wird. Mit diesen Werten bestimmt der Komparator beim Sortieren seine Position in der Liste.

Probieren Sie es hier aus .

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

All das Array überprüfen :-(