Betrachten Sie den Vorgang des Auswählens einer verschachtelten Liste. Die Kommissionierung ist wie folgt definiert:

• Wenn es sich bei dem Argument um eine Liste handelt, nehmen Sie ein Element (gleichmäßig) zufällig aus der Liste und wählen Sie es aus.
• Wenn das Argument keine Liste ist, geben Sie es einfach zurück.

Eine Beispielimplementierung in Python:

import random
def pick(obj):
    if isinstance(obj, list):
        return pick(random.choice(obj))
    else:
        return obj

Der Einfachheit halber nehmen wir an, dass verschachtelte Listen nur Ganzzahlen oder weitere verschachtelte Listen enthalten.

Ausgehend von einer Liste ist es möglich, eine reduzierte Version zu erstellen, die nicht zu unterscheiden ist pick, dh bei Auswahl derselben werden mit derselben Wahrscheinlichkeit dieselben Ergebnisse erzielt.

Zum Beispiel, "Abflachen" der Liste

[1, 2, [3, 4, 5]]

ergibt die Liste

[1, 1, 1, 2, 2, 2, 3, 4, 5]

. Der Grund ist einfach Abflachen ungültig ist , weil Elemente der Unterlisten eine geringere Wahrscheinlichkeit wird ausgewählt haben, zB in der Liste [1, [2, 3]]der 1 eine gewählten 2/4 = 1/2 Chance, während 3 und 4 beide ein 1/4 haben Chance für jeden.

Beachten Sie auch, dass das Auswählen aus einer Singleton-Liste dem Auswählen aus einem Element entspricht und dass das Auswählen aus einer leeren Liste keine Bedeutung hat.

Die Herausforderung

Bei einer verschachtelten Liste nichtnegativer Ganzzahlen geben Sie eine abgeflachte Liste nichtnegativer Ganzzahlen zurück, aus der Sie mit der gleichen Wahrscheinlichkeit dieselben Ergebnisse erzielen.

Das ist Code-Golf , also gewinnt die kürzeste gültige Antwort (gemessen in Bytes).

Spezifikationen

• Die Eingaben [2, 3, 4], [2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]und [2, [3, 3], [[4]]]sind äquivalent (dh sie sollten äquivalente Ergebnisse liefern).
• Die Ausgänge [2, 2, 2, 2, 3, 3, 3, 3]und [2, 3]sind äquivalent (dh es könnte einer ausgegeben werden).
• Sie können davon ausgehen, dass in den Listen nur Zahlen im Bereich von 1 bis 100 enthalten sind.
• Sie können davon ausgehen, dass die Eingabe der obersten Ebene eine Liste ist, dh 2keine gültige Eingabe.
• Sie können jede vernünftige Darstellung von verschachtelten Listen verwenden, zum Beispiel:
  [1, [2, 3]], 1 {2 3}, "[ 1 [ 2 3 ] ]"etc.
• Anstelle einer Liste können Sie ein Multiset oder eine Zuordnung ausgeben oder, da nur Zahlen im Bereich von 1 bis 100 zulässig sind, eine Liste mit Ganzzahlen der Länge 100, die Mengen darstellen.

Testfälle

Beachten Sie, dass die aufgelisteten Ausgaben nur eine gültige Möglichkeit sind. In den Spezifikationen ist angegeben, was eine gültige Eingabe oder Ausgabe darstellt.

format:
input -> output
[3]                          -> [3]
[1, [1, 1]]                  -> [1]
[1, [2, 3]]                  -> [1, 1, 2, 3]
[2, 3, [4, [5, 5, 6], 6, 7]] -> [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7]
[[1, 1, 2], [2, 3, 3]]       -> [1, 2, 3]
[[1, 1, 2], [2, 3, 3, 3]]    -> [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]

Wolfram Language (Mathematica) , 41 20 Bytes

Flatten@*Tuples//@#&

Probieren Sie es online! Ignorieren Sie die vielen Warnungen, am Ende klappt alles.

Wie es funktioniert

Eine Liste der Tiefe 2 , wie beispielsweise {{1,2},{3},{4,5,6}}, Tupleswird die Liste generieren , {{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}um alle Möglichkeiten entsprechen , die von einem Element zu holen {1,2} und ein Element aus holen {3} und ein Element aus zu holen {4,5,6}.

Wenn wir Flattendies, dann bekommen wir alle die Elemente mit den richtigen Frequenzen, da ein Element von der Kommissionierung eines von {1,2}, {3}oder {4,5,6}entspricht ein Element aus allen von ihnen zu sammeln, dann die Wahl , die man zu halten.

Wir //@wenden dies auf alle Ebenen der Eingabe an. Dabei beklagt sich Mathematica sehr, weil es Atome wie 17in verwandelt Tuples[17], was eigentlich keine Sache sein soll. Diese vereinfachen aber später das richtige Ergebnis ( Tupleswird gerne Tuples[17]als Liste der Länge 1 behandelt, auch wenn sie einen anderen Kopf als hat List), sodass die Beschwerde irrelevant ist.

Python 2 , 105 102 99 Bytes

g=lambda y=[],*z:[w+[n]for n in y for w in g(*z)]or[y]
f=lambda x:x<[]and[x]or sum(g(*map(f,x)),[])

Probieren Sie es online!

Gelee , 9 8 Bytes

߀Œp$¬¡F

Probieren Sie es online!

Wie es funktioniert

߀Œp$¬¡F  Main link. Argument: x (array or positive integer)

     ¬    Compute elementwise logical NOT of x: a non-empty array for a non-empty array, 0 for a positive integer.
      ¡   Apply the link to the left once if ¬ returned a non-empty
          array, zero timed if it returned 0.
    $     Monadic chain:
߀            Map the main link over x.
  Œp          Take the Cartesian product.
       F  Flatten the result.

Gelee , 10 Bytes

L€P⁸ṁ€ẎµÐL

Probieren Sie es online!

Python 2 , 128 Bytes

def f(l,p=0):m=reduce(int.__mul__,[i*0<[]or len(i)for i in l]);return p*(p==l)or f(sum([(([i],i)[i*0>0]*m)[:m]for i in l],[]),l)

Probieren Sie es online!

Port meiner Gelee Antwort.

-12 danke an Jonathan Frech .

C (gcc) , 234 223 Bytes

h[9][101];o[101];n[9];l;L;e;main(x){for(;(x=scanf("%d",&e))>=0;x?++h[l][e],++n[l]:(e=getchar())-'['?e-']'?0:--l:++l>L&&++L);for(e=1,l=L+1;l--;){for(x=101;--x;o[x]+=e*h[l][x]);e*=n[l];}while(o[x]--?printf("%d ",x):++x<101);}

Probieren Sie es online!

Erläuterung:

h[9][101];  // <- number occurences per nesting level
o[101];     // <- number occurences in "flattened" array
n[9];       // <- number of entries per nesting level
l;          // <- current nesting level
L;          // <- max nesting level
e;          // <- multi-purpose temporary
main(x){    // x: multi-purpose temporary
    for(;
            // while not EOF try reading number
            (x=scanf("%d",&e))>=0;

            // number was read?
            x

                // then increment occurence and # entries in level
                ?++h[l][e],++n[l]

                // else read any character ... if not [
                :(e=getchar())-'['

                    // if not ]
                    ?e-']'

                        // do nothing
                        ?0

                        // else decrement nesting level
                        :--l

                    // else increment nesting level and adjust max level
                    :++l>L&&++L);

    // init factor in e to 1, iterate over nesting level from innermost
    for(e=1,l=L+1;l--;){

        // iterate over all numbers
        for(x=101;
                --x;

                // add factor times occurence on current level to output
                o[x]+=e*h[l][x]);

        // multiply factor by number of entries on current level
        e*=n[l];
    }

    // iterate over all numbers and output count times
    while(o[x]--?printf("%d ",x):++x<101);
}

Python 2 , 144 139 Bytes

def f(A,p):[F.append((len(A)*p,a))if a*0<[]else f(a,len(A)*p)for a in A]
F=[];f(input(),1);R=[]
for v in F:R+=max(F)[0]/v[0]*[v[1]]
print R

Probieren Sie es online!

JavaScript (ES6), 132 131 Bytes

f=A=>(_=(a,m)=>[].concat(...a.map(m)),n=1,A=A.map(a=>a.map?f(a):[a]),_(A,a=>n*=a.length),_(A,a=>_(a.map(x=>Array(n/a.length).fill(x)))))

f=A=>(_=(a,m)=>[].concat(...a.map(m)),n=1,A=A.map(a=>a.map?f(a):[a]),_(A,a=>n*=a.length),_(A,a=>_(a,x=>Array(n/a.length).fill(x))))

console.log( f( [3] ) )
console.log( f( [1, [1, 1]] ) )
console.log( f( [1, [2, 3]] ) )
console.log( f( [2, 3, [4, [5, 5, 6], 6, 7]] ) )
console.log( f( [[1, 1, 2], [2, 3, 3]] ) )
console.log( f( [[1, 1, 2], [2, 3, 3, 3]] ) )
console.log( f( [1, 2, [3, 4, 5], [6, 7]] ) )