Реализовать API для распределения вероятностей

9

Введение

В этой задаче ваша задача - реализовать набор простых функций, которые вместе образуют полезную мини-библиотеку для простых распределений вероятностей. Чтобы учесть некоторые из более эзотерических языков, которые люди любят использовать здесь, допустимы следующие реализации:

  1. Фрагмент кода, определяющий коллекцию именованных функций (или ближайших эквивалентов).
  2. Коллекция выражений, которые оценивают именованные или анонимные функции (или их ближайшие эквиваленты).
  3. Одно выражение, которое оценивает несколько именованных или анонимных функций (или ближайших эквивалентов).
  4. Набор независимых программ, которые принимают входные данные из командной строки, STDIN или ближайшего аналога и выводят в STDOUT или ближайший эквивалент.

Функции

Вы должны реализовать следующие функции, используя более короткие имена, если это необходимо.

  1. uniformпринимает в качестве входных данных два числа с плавающей запятой aи bи возвращает равномерное распределение [a,b]. Вы можете предположить, что a < b; дело a ≥ bне определено.
  2. blendпринимает в качестве входных сигналов трех вероятностных распределений P, Qи R. Он возвращает распределение вероятностей S, которое рисует значения x, yи zиз P, Qи R, соответственно, и дает, yесли x ≥ 0и zесли x < 0.
  3. overпринимает в качестве входных данных число с плавающей запятой fи распределение вероятностей Pи возвращает вероятность, которая x ≥ fимеет место для случайного числа, xвзятого из P.

Для справки, overможет быть определен следующим образом (в псевдокоде):

over(f, uniform(a, b)):
    if f <= a: return 1.0
    else if f >= b: return 0.0
    else: return (b - f)/(b - a)

over(f, blend(P, Q, R)):
    p = over(0.0, P)
    return p*over(f, Q) + (1-p)*over(f, R)

Вы можете предположить, что все распределения вероятностей, данные для этого over, построены с использованием uniformи blend, и что единственное, что пользователь собирается делать с распределением вероятностей, это передать его blendили over. Вы можете использовать любой удобный тип данных для представления распределений: списки чисел, строки, пользовательские объекты и т. Д. Единственное, что важно, это то, что API работает правильно. Кроме того, ваша реализация должна быть детерминированной, то есть всегда возвращать один и тот же вывод для одних и тех же входных данных.

Контрольные примеры

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

over(4.356, uniform(-4.873, 2.441)) -> 0.0
over(2.226, uniform(-1.922, 2.664)) -> 0.09550806803314438
over(-4.353, uniform(-7.929, -0.823)) -> 0.49676329862088375
over(-2.491, uniform(-0.340, 6.453)) -> 1.0
over(0.738, blend(uniform(-5.233, 3.384), uniform(2.767, 8.329), uniform(-2.769, 6.497))) -> 0.7701533851999125
over(-3.577, blend(uniform(-3.159, 0.070), blend(blend(uniform(-4.996, 4.851), uniform(-7.516, 1.455), uniform(-0.931, 7.292)), blend(uniform(-5.437, -0.738), uniform(-8.272, -2.316), uniform(-3.225, 1.201)), uniform(3.097, 6.792)), uniform(-8.215, 0.817))) -> 0.4976245638164541
over(3.243, blend(blend(uniform(-4.909, 2.003), uniform(-4.158, 4.622), blend(uniform(0.572, 5.874), uniform(-0.573, 4.716), blend(uniform(-5.279, 3.702), uniform(-6.564, 1.373), uniform(-6.585, 2.802)))), uniform(-3.148, 2.015), blend(uniform(-6.235, -5.629), uniform(-4.647, -1.056), uniform(-0.384, 2.050)))) -> 0.0
over(-3.020, blend(blend(uniform(-0.080, 6.148), blend(uniform(1.691, 6.439), uniform(-7.086, 2.158), uniform(3.423, 6.773)), uniform(-1.780, 2.381)), blend(uniform(-1.754, 1.943), uniform(-0.046, 6.327), blend(uniform(-6.667, 2.543), uniform(0.656, 7.903), blend(uniform(-8.673, 3.639), uniform(-7.606, 1.435), uniform(-5.138, -2.409)))), uniform(-8.008, -0.317))) -> 0.4487803553043079
Zgarb
источник
2
Можем ли мы использовать встроенные функции для их создания?
Мутадор
@ AndréMuta Я забыл, что Mathematica, вероятно, имеет встроенные модули для всего этого ... но я позволю им, если они следуют правилам.
Згарб
Что вы предлагаете для представления данных с плавающей запятой в BrainFuck?
flawr
@flawr Для языков, которые не имеют собственных чисел с плавающей запятой, вы можете использовать любую удобную кодировку для чисел с плавающей запятой в диапазоне от -10,0 до 10,0 (исключая), у которых не более 0,001 разницы между последовательными значениями. Вывод должен быть точным с точностью до 0,01 для тестовых случаев.
Згарб

Ответы:

1

CJam, 58 байт

{[\]}:U;
{[@]}:B;
{_,2={~1$-@@-\/0e>1e<}{6Yb@f*\.{O})[_1@-].*:+}?}:O;

Это постфиксные операторы, которые работают в стеке: 2.0 1.0 3.0 U Oесть over(2, uniform(1, 3)).

Счетчик очков

{[\]}сама функция, :U;присваивает ей имя Uи выскакивает. По сути, это не является частью функции, поэтому по правилу подсчета очков 2 мне нужно будет только сосчитать {[\]}. Bопределяется аналогично.

Тем не менее, Oэто рекурсивно, и если я не укажу имя, нет способа рекурсивно. Так что здесь, я был бы склонен считать :O;часть. Тогда мой счет в 5+5+48=58байтах.

объяснение

Uвыскакивает два аргумента и делает пару в обратном порядке: a b => [b a].

Bвыскакивает три аргумента и делает тройным в повернутом порядке: a b c => [b c a].

OСтруктура выглядит следующим образом:

{             }:O;   Define O as this function:
 _,2=        ?       If the argument list's length is 2:
     {~Γ}            Append the list to the stack and execute subprogram Γ.
         {~Δ}        Else, do the same, but execute subprogram Δ.

Подпрограмма Г обрабатывает равномерные распределения:

Executed ops      Explanation   Stack contents
============      ===========   ==============
                  Initial       f; b; a
1$                Copy b        f; b; a; b
  -               Difference    f; b; (a-b)
   @@             Rotate x2     (a-b); f, b
     -            Difference    (a-b); (f-b)
      \/          Flip divide   (f-b)/(a-b)
        0e>       Clamp low     max(0, (f-b)/(a-b))
           1e<    Clamp high    min(1, max(0, (f-b)/(a-b)))

Подпрограмма Δ обрабатывает смешанные распределения:

Executed ops              Explanation    Stack contents
============              ===========    ==============
                          Initial        f; [Q R P]
6Yb                       Push [1,1,0]   f; [Q R P]; [1 1 0]
   @                      Rotate         [Q R P]; [1 1 0]; f
    f*                    Multiply each  [Q R P]; [f f 0]
      \                   Swap           [f f 0]; [Q R P]
       .{O}               Pairwise O     [q r p]
           )              Uncons         [q r] p
            [_1@-]        [p, 1-p]       [q r] [p 1-p]
                  .*:+    Dot product    q*p+r*(1-p)
Линн
источник
2

Руби, 103

u=b=->*a{a}
o=->f,d{d[2]?(p=o[0,d[0]])*o[f,d[1]]+(1-p)*o[f,d[2]]:(f<a=d[0])?1:(f>b=d[1])?0:(b-f)/(b-a)}

Определяет три лямбды, u, b, и o. uи bпросто создайте двухэлементные и трехэлементные массивы соответственно. oПредполагается, что двухэлементный массив является равномерным распределением, а трехэлементный массив представляет собой смесь трех распределений. В последнем случае он вызывает себя рекурсивно.

histocrat
источник
2

МАТЛАБ, 73

Время немного «функционального программирования» в MATLAB. Это 3 анонимные функции. Uniform и blend называются так же, как примеры, но для overаргументов их нужно поменять местами. На самом деле мне не нужны overпервые две возвращаемые функции, но формальность feval- это функция, которая может вызывать функцию.

%uniform
@(a,b)@(x)(x<b)*min(1,(b-x)/(b-a))
%blend
@(P,Q,R)@(x)P(0)*(Q(x)-R(x))+R(x)
%over
@feval

Теперь система синтаксического анализа и оценки MATLAB немного не очень удобна, если не сказать больше. Он не позволяет вам напрямую вызывать функцию, которая была возвращена из функции. Вместо этого нужно сначала сохранить результат в переменной. Четвёртый пример можно сделать следующим образом:

x=uniform(-5.233,3.384);y=uniform(2.767,8.329);z=uniform(-2.769,6.497);over(blend(x,y,z),0.738)

Тем не менее, можно обойти это, используя fevalдля вызова всех функций. Если используются следующие определения, то примеры могут быть оценены именно так, как они написаны.

uniform=@(a,b)@(x)(x<b)*min(1,(b-x)/(b-a))
blend=@(P,Q,R)@(x)feval(P,0)*(feval(Q,x)-feval(R,x))+feval(R,x)
over=@(x,f)feval(f,x)
feersum
источник
Функции делают функции ... как извращенно!
Луис Мендо
1

Mathematica, 129 116 байтов

u=UniformDistribution@{##}&;b=If[x<0,z,y]~TransformedDistribution~{x\uF3D2#,y\uF3D2#2,z\uF3D2#3}&;o=Probability[x>=#,x\uF3D2#2]&

u, bи oесть uniform, blendи overсоответственно. Оболочка над стандартными функциями. Замените \uF3D2s трехбайтовым символом. Просто возвращается 0и 1для случаев 1, 4 и 7.

LegionMammal978
источник
1

Python, 146 байт

u=lambda*a:a
b=u
x=lambda f,a,b:[int(f<=a),(b-f)/(b-a)][a<f<b]
y=lambda f,p,q,r:o(0,p)*o(f,q)+(1-o(0,p))*o(f,r)
o=lambda f,p:[x,y][len(p)-2](f,*p)

Та же стратегия, что и у гистократского Ruby-ответа, но в Python. Делать рекурсию без Z-комбинатора (что было бы дорого), xи yопределяются как вспомогательные функции, которые оценивают overдля кортежей аргументов 2 и 3 длины ( uniformиblend аргументы соответственно).

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

Mego
источник
0

Matlab, 104 байта

Я надеюсь, что это все еще верно, так как это работает только для дистрибутивов с поддержкой в ​​[-10,10], что является требованием для языков, которые не поддерживают плавающую точку. Опорный вектор и точность можно легко отрегулировать, просто изменив соответствующие числа. u,o,bдля uniform,blend,over. PDF просто представлен в виде дискретного вектора. Я думаю, что этот подход можно легко перенести на другие языки.

D=1e-4;X=-10:D:10;
u=@(a,b)(1/(b-a))*(a<X&X<b);
o=@(x,d)sum(d.*(X>x))*D;
b=@(p,q,r)o(0,p).*q+(1-o(0,p)).*r;

Вы можете проверить их, если сначала определите эти функции, а затем просто вставьте этот код:

[o(4.356, u(-4.873, 2.441)) , 0.0;
o(2.226, u(-1.922, 2.664)) , 0.09550806803314438;
o(-4.353, u(-7.929, -0.823)) , 0.49676329862088375;
o(-2.491, u(-0.340, 6.453)) , 1.0;
o(0.738, b(u(-5.233, 3.384), u(2.767, 8.329), u(-2.769, 6.497))) , 0.7701533851999125;
o(-3.577, b(u(-3.159, 0.070), b(b(u(-4.996, 4.851), u(-7.516, 1.455), u(-0.931, 7.292)), b(u(-5.437, -0.738), u(-8.272, -2.316), u(-3.225, 1.201)), u(3.097, 6.792)), u(-8.215, 0.817))) , 0.4976245638164541;
o(3.243, b(b(u(-4.909, 2.003), u(-4.158, 4.622), b(u(0.572, 5.874), u(-0.573, 4.716), b(u(-5.279, 3.702), u(-6.564, 1.373), u(-6.585, 2.802)))), u(-3.148, 2.015), b(u(-6.235, -5.629), u(-4.647, -1.056), u(-0.384, 2.050)))) , 0.0;
o(-3.020, b(b(u(-0.080, 6.148), b(u(1.691, 6.439), u(-7.086, 2.158), u(3.423, 6.773)), u(-1.780, 2.381)), b(u(-1.754, 1.943), u(-0.046, 6.327), b(u(-6.667, 2.543), u(0.656, 7.903), b(u(-8.673, 3.639), u(-7.606, 1.435), u(-5.138, -2.409)))), u(-8.008, -0.317))) , 0.4487803553043079]
flawr
источник
Matlab имеет поддержку FP, поэтому я думаю, что это будет недействительным.
LegionMammal978
Я не решаюсь разрешить это, поскольку Matlab изначально поддерживает числа с плавающей запятой. Если вы можете заменить Xи Dна MIN_FLOATи MAX_FLOAT(или как их называет Matlab), то это правильный подход.
Zgarb
Да, вы можете использовать realmax/ realmin, вы даже можете создать вектор, который проходит через все числа с плавающей запятой, если у вас достаточно памяти.
flawr