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 code-golf, 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]