Probabilidade de todas as combinações de determinados eventos

18

Dada uma sequência de eventos com probabilidades entre 0,0 e 1,0, gere e calcule a probabilidade de cada combinação ocorrer. Você pode presumir que uma sequência de números seja fornecida em qualquer construção que o idioma escolhido forneça.

Aqui está um exemplo; você pode presumir que o comprimento das combinações da sequência cabe na memória:

{ 0.55, 0.67, 0.13 }

O programa deve imprimir cada combinação e a probabilidade associada dessa sequência. Um 1 indica que o evento nesse índice da sequência de entrada ocorreu e um 0 indica que esse evento não ocorreu. A saída desejada está abaixo (não me importo com a impressão do trabalho, isso é apenas para fins informativos do algoritmo):

[0,0,0] = (1 - 0.55) * (1-0.67) * (1-0.13) = 0.129195
[0,0,1] = (1 - 0.55) * (1-0.67) * (0.13)   = 0.019305
[0,1,0] = (1 - 0.55) * (0.67)   * (1-0.13) = 0.262305
[0,1,1] = (1 - 0.55) * (0.67)   * (0.13)   = 0.039195
[1,0,0] = (0.55)     * (1-0.67) * (1-0.13) = 0.157905
[1,0,1] = (0.55)     * (1-0.67) * (0.13)   = 0.023595
[1,1,0] = (0.55)     * (0.67)   * (1-0.13) = 0.320595
[1,1,1] = (0.55)     * (0.67)   * (0.13)   = 0.047905

Esse problema está tangencialmente relacionado ao cálculo de um "produto cartesiano".

Lembre-se, isso é código-golfe, portanto o código com o menor número de bytes vence.

Mark Johnson
fonte
3
Bem-vindo à programação de quebra-cabeças e código de golfe, e o primeiro desafio!
Maçaneta da porta
Seria [0.129195, 0.019305, 0.262305, ..., 0.047905]suficiente como saída ou é [0,0,0], [0,0,1], ...necessário?
Laikoni
@Laikoni Essa saída é boa. A porção de saída não é a carne do problema.
Mark Johnson
A saída pode estar na ordem inversa?
Luis Mendo
@LuisMendo Claro, por que não.
Mark Johnson

Respostas:

8

Haskell, 86 bytes

unlines.map(\p->show(fst<$>p)++" = "++show(product$snd<$>p)).mapM(\x->[(0,1-x),(1,x)])

Exemplo de uso:

Prelude> putStrLn $ unlines.map(\p->show(fst<$>p)++" = "++show(product$snd<$>p)).mapM(\x->[(0,1-x),(1,x)]) $ [0.55, 0.67, 0.13]
[0,0,0] = 0.12919499999999998
[0,0,1] = 1.9304999999999996e-2
[0,1,0] = 0.262305
[0,1,1] = 3.9195e-2
[1,0,0] = 0.157905
[1,0,1] = 2.3595e-2
[1,1,0] = 0.320595
[1,1,1] = 4.790500000000001e-2

A maioria dos bytes é gasta na formatação de saída. Se você está interessado apenas no vetor de probabilidade, são apenas 29 bytes:

map product.mapM(\x->[1-x,x])

Como funciona:

                    mapM(\x->[(0,1-x),(1,x)])   -- for each number x in the input
                                                -- list make either the pair (0,1-x)
                                                -- or (1,x). Build a list with
                                                -- all combinations

    map(\p->                    )               -- for each such combination p
          show(fst<$>p)                         -- print the first elements
          ++" = "++                             -- then the string " = "
          show(product$snd<$>p)                 -- then the product of the second
                                                -- elements

unlines                                         -- joins with newlines
nimi
fonte
Isso é legal; Fiquei curioso para saber se haveria uma maneira realmente curta e puramente funcional de fazer isso. Você conhece C # ou F #? Estou curioso para saber como seria o mesmo algoritmo nessas linguagens, pois não estou familiarizado com a sintaxe Haskell.
Mark Johnson
@ MarkJohnson: não, desculpe, eu não sei nem C # nem F #.
N
5

Mathematica, 46 45 bytes

(s=#;1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s)&

Leva uma lista. Até funciona para a lista vazia {}, para a qual a saída é {1}.

Caso de teste:

%[{0.55, 0.67, 0.13}]
{0.129195, 0.019305, 0.262305, 0.039195, 0.157905, 0.023595, 0.320595, 0.047905}

Explicação

Dada uma lista de probabilidades se uma lista de bits bcom 0denotando "não ocorreu" e 1denotando "ocorreu", a lista de probabilidades a serem multiplicadas é dada por

1 - b - s

até assinar. Se, em vez disso, 0denota "ocorreu" e 1"não ocorreu", isso simplifica a

b - s

então nós:

                      {1,0}~Tuples~Length@s   (* Generate all possible bit combinations *)
              (#-s)&/@{1,0}~Tuples~Length@s   (* Generate probabilities to be multiplied
                                                  up to sign *)
     1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s   (* Correct sign and multiply;
                                                 1##& is short for Times *)
(s=#;1##&@@Abs[#-s]&/@{1,0}~Tuples~Length@s)& (* Assign s to first argument of function,
                                                 done separately to avoid clash
                                                 with inner function *)
u54112
fonte
4

Perl, 42 40 bytes

Inclui +1 para -a

Dê números sobre STDIN:

perl -M5.010 combi.pl <<< "0.55 0.67 0.13"

saídas

0.129195
0.019305
0.262305
0.039195
0.157905
0.023595
0.320595
0.047905

combi.pl:

#!/usr/bin/perl -a
$"=")\\*({1-,}";say eval for<({1-,}@F)>
Ton Hospel
fonte
4

MATL , 12 11 bytes

TF-|Z}&Z*!p

Entrada é um vetor de coluna, com o formato [0.55; 0.67; 0.13]

Experimente online!

TF    % Push [1, 0]
-     % Subtract from implicit input (column array), with broadcast. Gives a 2-col
      % matrix where the first column is the input minus 1 and the second is the input
|     % Absolute value
Z}    % Split the matrix into its rows
&Z*   % Cartesian product of all resulting. This gives a matrix as result, with each
      % "combination" on a different row
!p    % Product of each row. Implicitly display
Luis Mendo
fonte
3

Perl, 116 bytes

for(glob"{0,1}"x(@a=split/ /,<>)){@c=split//;$d=1;$d*=@c[$_]?$a[$_]:1-$a[$_]for 0..$#a;say"[".join(",",@c)."] = $d"}

Legível:

for(glob"{0,1}"x(@a=split/ /,<>)){
    @c=split//;
    $d=1;$d*=@c[$_]?$a[$_]:1-$a[$_]for 0..$#a;
    say"[".join(",",@c)."] = $d"
}

Cria uma lista de todas as combinações possíveis de 0s e 1s de comprimento igual ao número de parâmetros de entrada (por exemplo, para o exemplo acima, seria de comprimento 3) e calcula cada probabilidade.

Agradeço ao @Dada por me mostrar o que a globfunção pode fazer, mesmo que eu não tenha 100% de certeza de que entendi como isso é feito.

Saída de amostra:

[0,0,0] = 0.129195
[0,0,1] = 0.019305
[0,1,0] = 0.262305
[0,1,1] = 0.039195
[1,0,0] = 0.157905
[1,0,1] = 0.023595
[1,1,0] = 0.320595
[1,1,1] = 0.047905
Gabriel Benamy
fonte
1
-aem vez de (@a=split/ /,<>)...
Dada
3

R, 72 69 bytes

Pega a entrada de stdin e retorna um vetor R de probabilidades.

apply(abs(t(expand.grid(rep(list(1:0),length(x<-scan())))-x)),1,prod)

Edit: Removida uma transposição desnecessária, a matriz de permutação agora é a versão transposta da abaixo e as probabilidades são calculadas como o produto em colunas e não em linhas. Exemplo de saída:

[1] 0.129195 0.157905 0.262305 0.320595 0.019305 0.023595 0.039195 0.047905

Observe que as probabilidades estão em uma ordem diferente devido ao fato de que a matriz de permutação gerada por expand.gridproduz o seguinte (a geração dessa matriz provavelmente pode ser alterada usando pacotes externos):

1    1    1    1
2    0    1    1
3    1    0    1
4    0    0    1
5    1    1    0
6    0    1    0
7    1    0    0
8    0    0    0

A primeira probabilidade corresponde ao resultado invertido da primeira linha na matriz acima e a segunda à segunda linha invertida etc. A formatação da saída para ver isso ainda mais claramente torna o programa mais longo (164 bytes):

m=expand.grid(rep(list(1:0),length(x<-scan())))
cat(paste0("[",apply(abs(m-1),1,function(x)paste0(x,collapse=",")),"] = ",apply(abs(t(t(m)-x)),1,prod),"\n"),sep="")

que produz:

[0,0,0] = 0.129195
[1,0,0] = 0.157905
[0,1,0] = 0.262305
[1,1,0] = 0.320595
[0,0,1] = 0.019305
[1,0,1] = 0.023595
[0,1,1] = 0.039195
[1,1,1] = 0.047905
Billywob
fonte
Eu estava trabalhando em minha própria resposta para isso, mas não consegui encontrar uma solução limpa. Ótimo uso de expand.grid! Eu acho que isso applypode funcionar tanto em quadros de dados quanto em matrizes, portanto seu código deve funcionar sem o t(t(...)), o que economizará 6 bytes.
Rbdbull #
@rturnbull Observe que tnão está relacionado a nenhum quadro de dados, mas para permitir a subtração do vetor de probabilidade da matriz de permutação (com diferentes dimensões). Pelo menos um deles é necessário devido à maneira como R lida com essas operações vetorizadas, mas eu provavelmente poderia remover a transposição externa e aplicar o produto sobre as colunas. Será atualizado amanhã
Billywob 6/06
2

J, 14 bytes

-.([:,*/)/@,.]

Uso

   f =: -.([:,*/)/@,.]
   f 0.55 0.67 0.13
0.129195 0.019305 0.262305 0.039195 0.157905 0.023595 0.320595 0.047905

Explicação

-.([:,*/)/@,.]  Input: array P
-.              Complement (1-x) for each x in P
             ]  Identity, get P
           ,.   Interleave to make pairs [(1-x), x]
  (     )/@     Reduce from right-to-left by
      */          Forming the multiplication table
   [:,            Flattening the result
milhas
fonte
Você pode transformar |*//0.55 0.67 0.13-/0 1em um trem?
Adám 14/11/16
2

Pitão, 10 bytes

*MaVLQ^U2l

Experimente online: Demonstração

Explicação:

*MaVLQ^U2lQ   implicit Q at the end (Q = input list)
      ^U2lQ   repeated Cartesian product of [0, 1] with itself length(Q)-times
              this gives all combinations of 0s and 1s
  aVLQ        absolute difference between these 0-1-vectors with Q
*M            fold the vectors by multiplication
Jakube
fonte
1

C, 110 bytes

i,k;f(float* a,int n){for(k=0;k<1<<n;++k){float p=1;for(i=0;i<n;++i)p*=k&(1<<i)?a[i]:1-a[i];printf("%f,",p);}}

Ungolfed:

i,k;f(float* a,int n){ 
 for(k=0; k<1<<n; ++k){
  float p=1;
  for (i=0; i<n; ++i)
   p*=k&(1<<i)?a[i]:1-a[i];
  printf("%f,",p);
 }
}

Funciona até 32 itens, + 5 + 1 bytes para 64 itens (declare long k;e adicione Lno primeiro loop para que k<1L<<N).

Karl Napf
fonte
1
Para> 32 itens, C requer o literal "L" no *1*<<nou isso é apenas uma coisa de C ++?
Mark Johnson
@ MarkJohnson sim, eu acho que exigiria.
Karl Napf
1

05AB1E , 8 bytes

<Äæ¹æR+P

Experimente online!

 <Äæ¹æR+P  # Main link (Input is [.1,.2])
 ###########
 <Ä        # Invert input, take the abs value.
           # Stack is [.9,.8]
   æ¹æ     # Powerset of both inverted and original arrays.
           # Stack is [[],[.1],[.2],[.1,.2]],[[],[.9],[.8],[.9,.8]]
      R+   # Reverse original array, add arrays together.
           # Stack is [.9,.8],[.1,.8],[.2,.9],[.1,.2]
        P  # For each sub array, push product.
           # Final Result: [0.02, 0.18, 0.08, 0.72]
           # E.G.          [  11,   10,   01,   00]
Urna de polvo mágico
fonte
1

JavaScript (Firefox 30-57), 57 bytes

f=([p,...a])=>1/p?[for(q of[1-p,p])for(b of f(a))q*b]:[1]

Retorna uma matriz de todas as probabilidades. Se você deseja a matriz de eventos também, então para 86 bytes:

f=([p,...a])=>1/p?[for(e of'01')for(b of f(a))[[+e,...b[0]],(+e?p:1-p)*b[1]]]:[[[],1]]

Se você receber os eventos como uma sequência, serão apenas 80 bytes:

f=([p,...a])=>1/p?[for(e of'01')for(b of f(a))[e+b[0],(+e?p:1-p)*b[1]]]:[['',1]]

Subtraia dois bytes para 1/cada solução se a probabilidade nunca for zero.

Neil
fonte
Como você executaria isso em um <script></script>bloco? Estou tendo problemas com o primeiro "por" ser inesperado?
Mark Johnson
@ MarkJohnson Desde que você esteja usando o Firefox 30 ou posterior, ele deve funcionar.
911 Neil
0

Perl 6, 24 19 bytes de Latin-1

{[*] 1 «-»@_ «|»@_}

Código mais antigo:

{[*] map {1-$^a|$^a},@_}

Esta é uma função. Use-o assim:

{[*] 1 «-»@_ «|»@_}(0.55, 0.67, 0.13)

para obter:

any(any(any(0.129195, 0.019305), any(0.262305, 0.039195)), any(any(0.157905, 0.023595), any(0.320595, 0.047905)))

Explicação do código mais antigo:

[*]          multiply together all array elements
map          but first transform each element via
{1-$^a|$^a}  considering both 1 minus the value and the value
,@_          of the function input

O código mais recente é basicamente o mesmo, apenas usando a sintaxe do terser:

[*]          multiply together all array elements
1 «-»@_      of the array formed by subtracting the argument from 1
«|»@_        pointwise considering both that and the original array

O mapa gera uma matriz cheia de anyconstruções, que se multiplicam em anyconstruções maiores , resolvendo o problema perfeitamente, sem precisar de um loop.

Não é o idioma mais curto para o programa, mas é uma tradução muito direta do problema.


fonte
0

Dyalog APL , 10 bytes

Nova Solução

Origem do índice independente. Função anônima. Leva a lista de probabilidades como argumento.

∘.×/⊢,¨1-⊢

∘.×/ A redução do produto cartesiano

os valores do argumento

cada um emparelhado com

1-⊢ os valores do argumento do complemento (lit. um menos os valores do argumento)

TryAPL online!


Solução antiga

Requer ⎕IO←0qual é o padrão em muitos sistemas. Solicita a lista de probabilidades.

|⎕∘.×.-⊂⍳2

Explicação

| valor absoluto de

a entrada, ɑ = [ ɑ ₁  ɑ ₂  ɑ ]

∘.×.-tensor interno modificado multiplicado, ( ɑ ₁ - b ₁) ⊗ ( ɑ ₂ - b ₂) ⊗ ( ɑ ₃ - b ₃), com

⊂⍳2a lista anexa b = [[0 1]]

Definição matemática

Como b é delimitado, é escalar e, portanto, estendido ao comprimento de ɑ , ou seja, 3, de modo que toda a expressão é

A = │ ( ɑ ₁ - b ) ⊗ ( ɑ ₂ - b ) ⊗ ( ɑ ₃ - b ) │ =

 │ ( ɑ ₁ - [0,1]) ⊗ ( ɑ ₂ - [0,1]) ⊗ ( ɑ ₃ - [0,1]) │ =

 │ [ ɑ ₁, ɑ ₁ - 1] ⊗ [ ɑ ₂ , ɑ ₂ - 1] ⊗ [ ɑ ₃, ɑ ₃ - 1] │ =

 ⎢ ⎡ ⎡   ɑɑɑ₃ ⎤ ⎡   ɑɑ ₂ ( ɑ ₃-1) ⎤ ⎤ ⎥
 ⎢ ⎢ ⎣  ɑ ₁ ( ɑ ₂-1) ɑ ₃ ⎦ ⎣  ɑ ₁ ( ɑ ₂-1) ( ɑ ₃-1) ⎦ ⎥ ⎥
 ⎢ ⎢ ⎡ ( ɑ ₁-1) ɑɑ ₃ ⎤ ⎡ ( ɑ ₁-1) ɑ ₂ ( ɑ ₃-1) ⎥ ⎥ ⎤
 ⎢ ⎣ ⎣ ( ɑ ₁-1) ( ɑ ₂-1) ɑ ₃⎦ ⎣ ( ɑ ₁-1) ( ɑ ₂-1) ( ɑ ₃-1) ⎦ ⎦

TryAPL online!

Notas (aplica-se à solução antiga e à nova)

O programa e a fórmula funcionam para qualquer número ( n ) de variáveis ​​e retornam uma matriz n- dimensional de comprimento 2 em todas as dimensões. Com três variáveis, a probabilidade de um resultado específico
P ( p , q , r ) = A p , q , r
que pode ser convenientemente selecionado da matriz com (⊃A)[p;q;r]extraído comp q r⌷⊃A

Por exemplo, 1 1 0⌷⊃|0.55 0.67 0.13∘.×.-⊂⍳2dá- P (55%, 67%, ¬13%) = 1,9305%

Adão
fonte
0

PHP, 105 97 94 93 87 bytes

for(;$i<2**$c=count($a=$argv)-$p=1;$i+=print-abs($p))for(;$c;)$p*=$a[$c--]-!($i>>$c&1);

Execute assim:

php -r 'for(;$i<2**$c=count($a=$argv)-$p=1;$i+=print-abs($p))for(;$c;)$p*=$a[$c--]-!($i>>$c&1);' -- .55 .67 .13 2>/dev/null;echo
> -0.129195-0.157905-0.262305-0.320595-0.019305-0.023595-0.039195-0.047905

Observe que a saída é pouco endian:

[0,0,0]
[1,0,0]
[0,1,0]
[1,1,0]
[0,0,1]
[1,0,1]
[0,1,1]
[1,1,1]

Explicação

for(
  ;
  $i<2**$c=                 # Iterate over possible combinations: 2^c,
    count($a=$argv)-$p=1;   #   where c is input length -p (set p to 1)
  $i+=print-abs($p)         # Increment i and print product after each
)                           #   iteration, dash separated
  for(
     ;
     $c;                    # Iterate over input ($c..0)
  )
    $p*=                    # Multiply the product by difference between:
      $a[$c--]-             # - The $c-th item of the input.
      !($i>>$c&1);          # - The $c-th bit of `$i`, negated (1 or 0)

Tweaks

  • Economizou 8 bytes usando a lógica binária para obter bits em vez de converter para string
  • Salvou um byte combinando a redefinição de $p1 com o cálculo de$c
  • Salvou um byte adicionando o resultado de print (1) ao $iinvés de incrementar
  • Salva um byte usando sublinhado como delimitador de saída
  • Salve um byte usando o sinal de menos como delimitador (não há chances negativas).
  • Salvo 6 bytes usando em $cvez de$$i
aross
fonte
0

C ++ 17, 137 131 129 bytes

Salvando 6 bytes declarando #define A auto, pela primeira vez que uma macro tão curta salva qualquer coisa. -2 bytes para usar #importe excluir o espaço antes<

#import<iostream>
#define A auto
A g(A r){std::cout<<r<<",";}A g(A r,A x,A...p){g(x*r,p...);g(r-x*r,p...);}A f(A...p){g(1,p...);}

Gera todas as combinações possíveis.

Ungolfed:

//base case to print the result
int g(auto r){std::cout << r << ",";}

//extract item from parameter pack
int g(auto r, auto x, auto... p) {
 g(x*r,p...);    //multiply with temp result and call with tail
 g(r-x*r,p...);  //same as above for (1-x)
}

//start of recursion, setting temp result to 1
int f(auto...p){g(1,p...);}

Uso:

f(0.55, 0.67, 0.13);
Karl Napf
fonte