Considere el proceso de "escoger" una lista anidada. La selección se define de la siguiente manera:

• Si el argumento es una lista, tome un elemento de la lista al azar (de manera uniforme) y selecciónelo.
• Si el argumento no es una lista, simplemente devuélvalo.

Un ejemplo de implementación en Python:

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

Para simplificar, asumimos que las listas anidadas solo contienen enteros o listas anidadas adicionales.

Dada cualquier lista, es posible crear una versión aplanada que no se puede distinguir pick, es decir, elegir de ella produce los mismos resultados, con la misma probabilidad.

Por ejemplo, "aplanar" la lista

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

produce la lista

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

. La razón por la que el aplanamiento simplemente no es válido es porque los elementos de las sublistas tienen una probabilidad menor de ser elegidos, por ejemplo, en la lista [1, [2, 3]]el 1 tiene una probabilidad de 2/4 = 1/2 de ser elegido, mientras que 3 y 4 tienen un 1/4 oportunidad cada uno.

También tenga en cuenta que elegir de una lista singleton es equivalente a elegir de su elemento, y que elegir de una lista vacía no tiene sentido.

El reto

Dada una lista anidada de enteros no negativos, devuelve una lista aplanada de enteros no negativos a partir de la cual la selección produce los mismos resultados con la misma probabilidad.

Este es el código de golf , por lo que gana la respuesta válida más corta (medida en bytes).

Especificaciones

• Las entradas [2, 3, 4], [2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]y [2, [3, 3], [[4]]]son equivalentes (es decir, deberían dar resultados equivalentes).
• Las salidas [2, 2, 2, 2, 3, 3, 3, 3]y [2, 3]son equivalentes (es decir, cualquiera de las dos podría salir).
• Puede suponer que solo los números en el rango inclusivo 1-100 estarán presentes en las listas.
• Puede suponer que la entrada de nivel superior será una lista, 2es decir, no es una entrada válida.
• Se puede utilizar cualquier representación razonable de listas anidadas, por ejemplo:
  [1, [2, 3]], 1 {2 3}, "[ 1 [ 2 3 ] ]", etc.
• En lugar de una lista, puede generar un conjunto múltiple o una asignación, o, dado que solo se permiten números en el rango 1-100, una lista de enteros de longitud 100 que representan cantidades.

Casos de prueba

Tenga en cuenta que las salidas enumeradas son solo una posibilidad válida; ver especificaciones para lo que constituye una entrada o salida válida.

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//@#&

Pruébalo en línea! Ignora las muchas advertencias, todo al final funciona.

Cómo funciona

Para una lista de profundidad 2 como {{1,2},{3},{4,5,6}}, Tuplesgenerará la lista {{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}correspondiente a todas las formas de elegir un elemento {1,2} y elegir un elemento {3} y elegir un elemento {4,5,6}.

Si hacemos Flattenesto, obtenemos todos los elementos con las frecuencias correctas, porque elegir un elemento de uno de ellos {1,2}, {3}o {4,5,6}es equivalente a elegir un elemento de todos ellos, y luego elegir cuál mantener.

Usamos //@para aplicar esto en todos los niveles de la entrada. En el proceso, Mathematica se queja mucho, porque está convirtiendo átomos como 17en Tuples[17], lo que realmente no se supone que sea una cosa. Pero estos se simplifican al resultado correcto más adelante ( Tupleses un placer tratarlo Tuples[17]como una lista de longitud 1, incluso si tiene una cabeza distinta List), por lo que la queja es irrelevante.

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)),[])

Pruébalo en línea!

Jalea , 9 8 bytes

߀Œp$¬¡F

Pruébalo en línea!

Cómo funciona

߀Œ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.

Jalea , 10 bytes

L€P⁸ṁ€ẎµÐL

Pruébalo en línea!

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)

Pruébalo en línea!

Puerto de mi respuesta de gelatina.

-12 gracias a 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);}

Pruébalo en línea!

Explicación:

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

Pruébalo en línea!

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