20
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ 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) \$\endgroup\$
    – Uriel
    Nov 6, 2017 at 20:39
  • \$\begingroup\$ @Uriel Sure; I'll reword it. \$\endgroup\$ Nov 7, 2017 at 0:52

8 Answers 8

8
\$\begingroup\$

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.

\$\endgroup\$
0
6
\$\begingroup\$

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

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.
    $     Monadic chain:
߀            Map the main link over x.
  Œp          Take the Cartesian product.
       F  Flatten the result.
\$\endgroup\$
1
\$\begingroup\$

Jelly, 10 bytes

L€P⁸ṁ€ẎµÐL

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ @Challenger5 sorry, no time for that yesterday \$\endgroup\$ Nov 7, 2017 at 12:24
1
\$\begingroup\$

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!

Port of my Jelly answer.

-12 thanks to Jonathan Frech.

\$\endgroup\$
2
  • \$\begingroup\$ I think type(i)==int can be i*0<[]. \$\endgroup\$ Nov 6, 2017 at 20:35
  • \$\begingroup\$ @JonathanFrech Sure, 0<[]...and type(i)==list can be i*0>0 ;) \$\endgroup\$ Nov 6, 2017 at 20:37
1
\$\begingroup\$

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;

            // 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);
}
\$\endgroup\$
1
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.