Подбери список

20

Рассмотрим процесс «выбора» вложенного списка. Комплектация определяется следующим образом:

  • Если аргумент является списком, возьмите элемент из списка случайным образом (равномерно) и выберите его.
  • Если аргумент не является списком, просто верните его.

Пример реализации в Python:

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

Для простоты мы предполагаем, что вложенные списки содержат только целые числа или дополнительные вложенные списки.

Для любого списка можно создать плоскую версию, которая неотличима pick, то есть выборка из нее дает одинаковые результаты с одинаковой вероятностью.

Например, «подбирать» список

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

выдает список

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

, Причина, по которой простое выравнивание является недопустимым, заключается в том, что элементы подсписков имеют меньшую вероятность выбора, например, в списке [1, [2, 3]]1 имеет шанс выбора 2/4 = 1/2, а 3 и 4 имеют 1/4 шанс каждого.

Также обратите внимание, что выбор из одноэлементного списка эквивалентен выбору из его элемента, и что выбор из пустого списка не имеет смысла.

Соревнование

При наличии вложенного списка неотрицательных целых чисел, вернуть уплощенный список неотрицательных целых чисел, из которого выборка дает одинаковые результаты с той же вероятностью.

Это код-гольф , поэтому выигрывает самый короткий действительный ответ (измеряемый в байтах).

Характеристики

  • Входы [2, 3, 4], [2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]и [2, [3, 3], [[4]]]эквивалентны (т.е. они должны давать эквивалентные результаты).
  • Выходы [2, 2, 2, 2, 3, 3, 3, 3]и [2, 3]эквивалентны (то есть любой из них может быть выведен).
  • Можно предположить, что в списках будут присутствовать только цифры в диапазоне от 1 до 100.
  • Вы можете предположить, что вход верхнего уровня будет списком, то 2есть не допустимым вводом.
  • Вы можете использовать любое разумное представление вложенных списков, например:
    [1, [2, 3]], 1 {2 3}, "[ 1 [ 2 3 ] ]"и т.д.
  • Вместо списка вы можете вывести мультимножество или отображение, или, поскольку разрешены только числа в диапазоне от 1 до 100, список целых чисел длиной 100, представляющий величины.

Тестовые случаи

Обратите внимание, что перечисленные выходы являются только одной допустимой возможностью; см спецификации для того, что представляет собой действительный вход или выход.

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]
code-golf number array-manipulation combinatorics probability-theory Esolanging Fruit
источник
Учитывая опцию кодирования длины и ограниченный диапазон, можем ли мы альтернативно вывести список из 100 элементов, изображающих вхождения каждого целого числа? (что приведет к множеству нулей для приведенных примеров)
Уриэль
@ Uriel Sure; Я перефразирую это.
Esolanging Fruit

Ответы:

8

Wolfram Language (Mathematica) , 41 20 байтов

Flatten@*Tuples//@#&

Попробуйте онлайн! Не обращайте внимания на множество предупреждений, в итоге все получится.

Как это устроено

Для получения списка глубины 2 , такие как {{1,2},{3},{4,5,6}}, Tuplesбудет генерировать список , {{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}соответствующие всем способы выбора элемента из {1,2} и выбора элемента из {3} и выбора элемента из {4,5,6}.

Если Flattenэто, то мы получаем все элементы с правильными частотами, так как собирание элемента из одного из {1,2}, {3}или {4,5,6}эквивалентно собирания элемента из всех из них, а затем выбрать один , который держать.

Мы используем, //@чтобы применить это на всех уровнях ввода. При этом Mathematica много жалуется, потому что превращает атомы, такие как 17в Tuples[17], что на самом деле не должно быть вещью. Но это упрощает до правильного результата позже ( Tuplesего можно рассматривать Tuples[17]как список длины 1, даже если у него есть голова, отличная от List), поэтому жалоба не имеет значения.

Миша лавров
источник
4

Желе , 9 8 байт

߀Œp$¬¡F

Попробуйте онлайн!

Как это устроено

߀Œ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.
Деннис
источник
1

Python 2 , 128 байт

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)

Попробуйте онлайн!

Порт моего желе ответа.

-12 спасибо Джонатану Фреху .

Эрик Outgolfer
источник
Я думаю, что type(i)==intможет быть i*0<[].
Джонатан Фрех
@JonathanFrech Конечно, 0<[]... и type(i)==listможет быть i*0>0;)
Эрик Outgolfer
1

C (gcc) , 234 223 байта

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

Попробуйте онлайн!

Объяснение:

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);
}
Феликс Палмен
источник
216 байт
floorcat
0

JavaScript (ES6), 132 131 байт

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

Показать фрагмент кода

darrylyeo
источник