Pick-flatten a list

Consider the process of "picking" a nested list. Picking is defined as follows:

• If the argument is a list, take an element from the list at random (uniformly), and pick from that.
• If the argument is not a list, simply return it.

An example implementation in Python:

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


For simplicity, we assume that nested lists only contain integers or further nested lists.

Given any list, it is possible to create a flattened version which is indistinguishable by pick, i.e. picking from it yields the same results, with the same probability.

For example, "pick-flattening" the list

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


yields the list

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


. The reason simply flattening is invalid is because elements of sub-lists have a lower probability of being chosen, e.g. in the list [1, [2, 3]] the 1 has a 2/4 = 1/2 chance of being chosen while 3 and 4 both have a 1/4 chance each.

Also note that picking from a singleton list is equivalent to picking from its element, and that picking from an empty list has no meaning.

The Challenge

Given a nested list of nonnegative integers, return a flattened list of nonnegative integers from which picking yields the same results with the same probability.

This is , so the shortest valid answer (measured in bytes) wins.

Specifications

• The inputs [2, 3, 4], [2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4], and [2, [3, 3], [[4]]] are equivalent (i.e. they should give equivalent results).
• The outputs [2, 2, 2, 2, 3, 3, 3, 3] and [2, 3] are equivalent (i.e. either one could be output).
• You can assume only numbers in the inclusive range 1-100 will be present in the lists.
• You can assume the top-level input will be a list, i.e. 2 is not a valid input.
• You can use any reasonable representation of nested lists, for example:
[1, [2, 3]], 1 {2 3}, "[ 1 [ 2 3 ] ]", etc.
• Instead of a list, you can output a multiset or a mapping, or, since only numbers in the range 1-100 are allowed, a length-100 list of integers representing quantities.

Test Cases

Note that the listed outputs are only one valid possibility; see specifications for what constitutes a valid input or output.

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]

• Given the length encoding option and the bounded range, may we alternatively output a list of 100 elements depicting the occurrences of every integer? (which will result with many zeros for the given examples) – Uriel Nov 6 '17 at 20:39
• @Uriel Sure; I'll reword it. – Esolanging Fruit Nov 7 '17 at 0:52

Wolfram Language (Mathematica), 41 20 bytes

Flatten@*Tuples//@#&


Try it online! Ignore the many warnings, it all works out in the end.

How it works

For a list of depth 2 such as {{1,2},{3},{4,5,6}}, Tuples will generate the list {{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}} corresponding to all the ways to pick an element from {1,2} and pick an element from {3} and pick an element from {4,5,6}.

If we Flatten this, then we get all the elements with the correct frequencies, because picking an element from one of {1,2}, {3} or {4,5,6} is equivalent to picking an element from all of them, then choosing which one to keep.

We use //@ to apply this at all levels of the input. In the process, Mathematica complains a lot, because it's turning atoms such as 17 into Tuples[17], which is really not supposed to be a thing. But these simplify to the right result later on (Tuples is happy to treat Tuples[17] as a list of length 1, even if it has a head other than List), so the complaining is irrelevant.

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


Try it online!

Jelly, 9 8 bytes

ß€Œp$¬¡F  Try it online! How it works ß€Œ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.
ß€            Map the main link over x.
Œp          Take the Cartesian product.
F  Flatten the result.


Jelly, 10 bytes

L€P⁸ṁ€ẎµÐL


Try it online!

• @Challenger5 sorry, no time for that yesterday – Erik the Outgolfer Nov 7 '17 at 12:24

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)


Try it online!

-12 thanks to Jonathan Frech.

• I think type(i)==int can be i*0<[]. – Jonathan Frech Nov 6 '17 at 20:35
• @JonathanFrech Sure, 0<[]...and type(i)==list can be i*0>0 ;) – Erik the Outgolfer Nov 6 '17 at 20:37

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


Try it online!

Explanation:

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;

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


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