Probabilité de toutes les combinaisons d'événements donnés

18

Étant donné une séquence d'événements avec des probabilités comprises entre 0,0 et 1,0, générez et dérivez la probabilité que chaque combinaison se produise. Vous pouvez supposer qu'une séquence de nombres est fournie dans la construction de votre langue choisie.

Voici un exemple; vous pouvez supposer que la longueur des combinaisons de la séquence tient en mémoire:

{ 0.55, 0.67, 0.13 }

Le programme doit imprimer chaque combinaison et la probabilité associée que cette séquence se produise. Un 1 indique que l'événement dans cet index de la séquence d'entrée s'est produit et un 0 signifie que cet événement ne s'est pas produit. La sortie souhaitée est ci-dessous (je ne me soucie pas d'imprimer le travail, c'est juste à des fins d'information de l'algorithme):

[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

Ce problème est tangentiellement lié au calcul d'un "produit cartésien".

N'oubliez pas qu'il s'agit de code-golf, donc le code avec le moins d'octets gagne.

Mark Johnson
la source
3
Bienvenue sur Programming Puzzles & Code Golf, et beau premier défi!
Poignée de porte
Serait [0.129195, 0.019305, 0.262305, ..., 0.047905]suffisant en sortie ou sont-ils [0,0,0], [0,0,1], ...nécessaires?
Laikoni
@Laikoni Cette sortie est très bien. La portion de sortie n'est pas la chair du problème.
Mark Johnson
La sortie peut-elle être dans l'ordre inverse?
Luis Mendo
@LuisMendo Bien sûr, pourquoi pas.
Mark Johnson

Réponses:

8

Haskell, 86 octets

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

Exemple d'utilisation:

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

La plupart des octets sont dépensés pour le formatage de sortie. Si vous n'êtes intéressé que par le vecteur de probabilité, il n'est que de 29 octets:

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

Comment ça fonctionne:

                    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
la source
C'est bien; J'étais curieux de savoir s'il y aurait un moyen purement fonctionnel très court de le faire. Connaissez-vous par hasard C # ou F #? Je suis curieux de savoir à quoi ressemblerait le même algorithme dans ces langues, car je ne connais pas du tout la syntaxe Haskell.
Mark Johnson
@MarkJohnson: non, désolé je ne connais ni C # ni F #.
nimi
5

Mathematica, 46 45 octets

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

Prend une liste. Fonctionne même pour la liste vide {}, pour laquelle la sortie est {1}.

Cas de test:

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

Explication

Compte tenu de la liste des probabilités set une liste de bits bavec 0indiquant « ne se produit pas » et 1indiquant « ne se », la liste des probabilités à multiplier est donnée par

1 - b - s

à signer. Si au lieu de cela 0dénote "s'est produit" et 1"ne s'est pas produit", cela simplifie

b - s

alors on:

                      {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
la source
4

Perl, 42 40 octets

Comprend +1 pour -a

Donnez des chiffres sur STDIN:

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

les sorties

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
la source
4

MATL , 12 11 octets

TF-|Z}&Z*!p

L'entrée est un vecteur colonne, au format [0.55; 0.67; 0.13]

Essayez-le en ligne!

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
la source
3

Perl, 116 octets

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

Lisible:

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

Crée une liste de toutes les combinaisons possibles de 0 et 1 de longueur égale au nombre de paramètres d'entrée (par exemple, pour l'exemple ci-dessus, il serait de longueur 3), puis calcule chaque probabilité.

Merci à @Dada de m'avoir montré ce que la globfonction peut faire, même si je ne suis pas sûr à 100% de comprendre comment cela fonctionne.

Exemple de sortie:

[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
la source
1
-aau lieu de (@a=split/ /,<>)...
Dada
3

R, 72 69 octets

Prend l'entrée de stdin et retourne un vecteur R de probabilités.

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

Edit: Suppression d'une transposition inutile, la matrice de permutation est maintenant la version transposée de celle ci-dessous et les probabilités sont calculées comme le produit par colonne plutôt que par ligne. Exemple de sortie:

[1] 0.129195 0.157905 0.262305 0.320595 0.019305 0.023595 0.039195 0.047905

Notez que les probabilités sont dans un ordre différent en raison du fait que la matrice de permutation générée par expand.gridproduit ce qui suit (la génération de cette matrice peut probablement être jouée à l'aide de packages externes):

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

La première probabilité correspond au résultat inversé de la première ligne de la matrice ci-dessus et la seconde à la deuxième ligne inversée, etc. Le formatage de la sortie pour voir cela rend encore plus clairement le programme plus long (164 octets):

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

qui produit à la place:

[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
la source
J'avais travaillé sur ma propre réponse à cela, mais je n'ai pas pu trouver de solution intéressante. Grande utilisation de expand.grid! Je pense que cela applypeut fonctionner sur les trames de données ainsi que sur les matrices, donc votre code devrait fonctionner sans le t(t(...)), ce qui vous fera économiser 6 octets.
rturnbull
@rturnbull Notez que cela tn'est lié à aucune trame de données mais pour permettre la soustraction du vecteur de probabilité de la matrice de permutation (avec différentes dimensions). Au moins l'un d'eux est nécessaire en raison de la façon dont R gère ces opérations vectorisées, mais je pourrais probablement supprimer la transposition externe et appliquer le produit sur des colonnes à la place.
Mettra à
2

J, 14 octets

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

Usage

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

Explication

-.([:,*/)/@,.]  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
miles
la source
Pouvez-vous faire |*//0.55 0.67 0.13-/0 1un train?
Adám
2

Pyth, 10 octets

*MaVLQ^U2l

Essayez-le en ligne: Démonstration

Explication:

*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
la source
1

C, 110 octets

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

Non golfé:

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

Fonctionne jusqu'à 32 éléments, + 5 + 1 octets pour 64 éléments (déclarez long k;et ajoutez Ldans la première boucle pour que k<1L<<N).

Karl Napf
la source
1
Pour> 32 éléments, C nécessite-t-il le littéral "L" sur le *1*<<nou est-ce juste une chose C ++?
Mark Johnson
@MarkJohnson oui, je suppose que cela nécessiterait.
Karl Napf
1

05AB1E , 8 octets

<Äæ¹æR+P

Essayez-le en ligne!

 <Äæ¹æ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]
Urne de poulpe magique
la source
1

JavaScript (Firefox 30-57), 57 octets

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

Renvoie un tableau de toutes les probabilités. Si vous voulez aussi le tableau des événements, alors pour 86 octets:

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

Si vous êtes autorisé à utiliser les événements sous forme de chaîne, cela ne représente que 80 octets:

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

Soustrayez deux octets pour 1/chaque solution si la probabilité ne sera jamais nulle.

Neil
la source
Comment feriez-vous cela dans un <script></script>bloc? Je rencontre des problèmes avec le premier "pour" inattendu?
Mark Johnson
@MarkJohnson Tant que vous utilisez Firefox 30 ou une version ultérieure, cela devrait fonctionner.
Neil
0

Perl 6, 24 19 octets de Latin-1

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

Code plus ancien:

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

Ceci est une fonction. Utilisez-le comme ceci:

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

obtenir:

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

Explication de l'ancien code:

[*]          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

Le code le plus récent est fondamentalement le même, utilisant simplement la syntaxe 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

La carte génère un tableau plein de anyconstructions, qui se multiplient en anyconstructions plus grandes , résolvant proprement le problème sans même avoir besoin d'une boucle.

Ce n'est pas la langue la plus courte du programme, mais c'est une traduction très directe du problème.


la source
0

Dyalog APL , 10 octets

Nouvelle solution

Indépendant de l'origine de l'index. Fonction anonyme. Prend la liste des probabilités comme argument.

∘.×/⊢,¨1-⊢

∘.×/ La réduction du produit cartésien sur

les valeurs d'argument

chacun jumelé avec

1-⊢ les valeurs des arguments complémentaires (lit. un moins les valeurs des arguments)

TryAPL en ligne!


Ancienne solution

Requiert ⎕IO←0ce qui est par défaut sur de nombreux systèmes. Demande la liste des probabilités.

|⎕∘.×.-⊂⍳2

Explication

| valeur absolue de

l'entrée, ɑ = [ ɑ ₁  ɑ ₂  ɑ ₃]

∘.×.-tenseur intérieur modifié multiplié, ( ɑ ₁ - b ₁) ⊗ ( ɑ ₂ - b ₂) ⊗ ( ɑ ₃ - b ₃), avec

⊂⍳2la liste jointe b = [[0 1]]

Définition mathématique

Comme b est inclus, il est scalaire, et donc étendu à la longueur de ɑ , à savoir 3, donc l'expression entière est

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 en ligne!

Remarques (s'applique à la fois à l'ancienne et à la nouvelle solution)

Le programme et la formule fonctionnent pour n'importe quel nombre ( n ) de variables et renvoient un tableau à n dimensions de longueur 2 dans chaque dimension. Avec trois variables, la probabilité d'un résultat spécifique
P ( p , q , r ) = A p , q , r
qui peut être commodément sélectionné dans le tableau avec(⊃A)[p;q;r] extrait avecp q r⌷⊃A

Par exemple, 1 1 0⌷⊃|0.55 0.67 0.13∘.×.-⊂⍳2donne P (55%, 67%, ¬13%) = 1,9305%

Adam
la source
0

PHP, 105 97 94 93 87 octets

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

Courez comme ceci:

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

Notez que la sortie est peu endienne:

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

Explication

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

  • 8 octets enregistrés en utilisant la logique binaire pour obtenir un bit au lieu de la convertir en chaîne
  • Enregistrement d'un octet en combinant la réinitialisation de $pà 1 avec le calcul de$c
  • Enregistrement d'un octet en ajoutant le résultat de print (1) à $iau lieu d'incrémenter
  • Enregistrement d'un octet en utilisant le soulignement comme délimiteur de sortie
  • Enregistrement d'un octet en utilisant le signe moins comme délimiteur (il n'y a aucune chance négative).
  • Enregistré 6 octets en utilisant $cau lieu de$$i
aross
la source
0

C ++ 17, 137 131 129 129 octets

Économiser 6 octets en déclarant #define A auto, pour la première fois, qu'une macro aussi courte enregistre quoi que ce soit. -2 octets pour utiliser #importet supprimer l'espace avant<

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

Génère toutes les combinaisons possibles.

Non golfé:

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

Usage:

f(0.55, 0.67, 0.13);
Karl Napf
la source