Wahrscheinlichkeit aller Kombinationen gegebener Ereignisse

18

Wenn eine Folge von Ereignissen mit Wahrscheinlichkeiten zwischen 0,0 und 1,0 gegeben ist, generieren Sie die Wahrscheinlichkeit, dass jede Kombination auftritt, und leiten Sie sie ab. Sie können davon ausgehen, dass eine Folge von Zahlen in dem von Ihnen gewählten Konstrukt enthalten ist.

Hier ist ein Beispiel; Sie können davon ausgehen, dass die Länge der Sequenzkombinationen in den Speicher passt:

{ 0.55, 0.67, 0.13 }

Das Programm gibt jede Kombination und die zugehörige Wahrscheinlichkeit des Auftretens dieser Sequenz aus. Eine 1 gibt an, dass das Ereignis in diesem Index der Eingabesequenz aufgetreten ist, und eine 0 gibt an, dass dieses Ereignis nicht aufgetreten ist. Die gewünschte Ausgabe ist unten (es ist mir egal, ob ich die Arbeit drucke, das ist nur zu Informationszwecken des Algorithmus):

[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

Dieses Problem hängt tangential mit der Berechnung eines "kartesischen Produkts" zusammen.

Denken Sie daran, das ist Code-Golf, also gewinnt der Code mit der geringsten Anzahl von Bytes.

Mark Johnson
quelle
3
Willkommen bei Programming Puzzles & Code Golf und schöne erste Herausforderung!
Türklinke
Wäre [0.129195, 0.019305, 0.262305, ..., 0.047905]als Ausgabe genug oder sind die [0,0,0], [0,0,1], ...nötig?
Laikoni
@ Laikoni Diese Ausgabe ist in Ordnung. Der Ausgabeanteil ist nicht das Fleisch des Problems.
Mark Johnson
Kann die Ausgabe in umgekehrter Reihenfolge erfolgen?
Luis Mendo
@ LuisMendo Sicher, warum nicht.
Mark Johnson

Antworten:

8

Haskell, 86 Bytes

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

Anwendungsbeispiel:

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

Die meisten Bytes werden für die Ausgabeformatierung ausgegeben. Wenn Sie sich nur für den Wahrscheinlichkeitsvektor interessieren, sind es nur 29 Bytes:

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

Wie es funktioniert:

                    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
quelle
Das ist ordentlich; Ich war neugierig, ob es eine wirklich kurze rein funktionale Möglichkeit geben würde, dies zu tun. Kennst du zufällig C # oder F #? Ich bin gespannt, wie derselbe Algorithmus in diesen Sprachen aussehen würde, da ich mit der Haskell-Syntax völlig unbekannt bin.
Mark Johnson
@ MarkJohnson: nein, sorry ich kenne weder C # noch F #.
nimi
5

Mathematica, 46 45 Bytes

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

Nimmt eine Liste. Funktioniert sogar für die leere Liste {}, für die die Ausgabe ist {1}.

Testfall:

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

Erläuterung

Wenn eine Liste von Wahrscheinlichkeiten sund eine Liste von Bits bmit der 0Bezeichnung "nicht aufgetreten" und 1"aufgetreten" gegeben ist, wird die Liste der zu multiplizierenden Wahrscheinlichkeiten mit gegeben

1 - b - s

bis zum unterschreiben. Wenn stattdessen 0"ist aufgetreten" und 1"ist nicht aufgetreten" bedeutet, vereinfacht sich dies

b - s

also wir:

                      {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
quelle
4

Perl, 42 40 Bytes

Beinhaltet +1 für -a

Gib Zahlen auf STDIN an:

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

Ausgänge

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)>
Tonne Hospel
quelle
4

MATL , 12 11 Bytes

TF-|Z}&Z*!p

Die Eingabe ist ein Spaltenvektor mit dem Format [0.55; 0.67; 0.13]

Probieren Sie es 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
quelle
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"}

Lesbar:

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

Erstellt eine Liste aller möglichen Kombinationen von Nullen und Einsen der Länge, die der Anzahl der Eingabeparameter entsprechen (im obigen Beispiel hätte sie beispielsweise die Länge 3), und berechnet dann jede Wahrscheinlichkeit.

Vielen Dank an @Dada, der mir gezeigt hat, was die globFunktion kann , auch wenn ich nicht zu 100% sicher bin, wie sie das macht.

Beispielausgabe:

[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
quelle
1
-astatt (@a=split/ /,<>)...
Dada
3

R, 72 69 Bytes

Übernimmt die Eingabe von stdin und gibt einen R-Vektor der Wahrscheinlichkeiten zurück.

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

Bearbeiten: Eine unnötige Transponierung wurde entfernt. Die Permutationsmatrix ist jetzt die transponierte Version der folgenden und die Wahrscheinlichkeiten werden eher als spaltenweise als als zeilenweise berechnet. Beispielausgabe:

[1] 0.129195 0.157905 0.262305 0.320595 0.019305 0.023595 0.039195 0.047905

Beachten Sie, dass die Wahrscheinlichkeiten in einer anderen Reihenfolge liegen, da die von generierte Permutationsmatrix expand.gridFolgendes ergibt (die Generierung dieser Matrix kann wahrscheinlich mit externen Paketen durchgeführt werden):

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

Die erste Wahrscheinlichkeit entspricht dem invertierten Ergebnis der ersten Zeile in der obigen Matrix und der zweiten der invertierten zweiten Zeile usw. Die Formatierung der Ausgabe, um dies noch deutlicher zu sehen, verlängert das Programm (164 Byte):

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

was stattdessen erzeugt:

[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
quelle
Ich hatte an meiner eigenen Antwort gearbeitet, aber ich konnte keine gute Lösung finden. Gute Verwendung von expand.grid! Ich denke, das applykann sowohl auf Datenrahmen als auch auf Matrizen angewendet werden, daher sollte Ihr Code ohne das funktionieren t(t(...)), was Ihnen 6 Bytes erspart.
Rturnbull
@rturnbull Beachten Sie, dass tes sich nicht um einen Datenrahmen handelt, sondern um die Subtraktion des Wahrscheinlichkeitsvektors von der Permutationsmatrix (mit unterschiedlichen Dimensionen). Mindestens eine davon wird aufgrund der Art und Weise benötigt, wie R diese vektorisierten Operationen verarbeitet, aber ich könnte wahrscheinlich die äußere Transponierung entfernen und das Produkt stattdessen über Spalten anwenden. Wird morgen aktualisiert
Billywob
2

J, 14 Bytes

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

Verwendung

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

Erläuterung

-.([:,*/)/@,.]  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
Meilen
quelle
Kannst du |*//0.55 0.67 0.13-/0 1einen Zug machen?
Adám
2

Pyth, 10 Bytes

*MaVLQ^U2l

Probieren Sie es online aus: Demonstration

Erläuterung:

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

Funktioniert mit bis zu 32 Elementen, + 5 + 1 Byte für 64 Elemente (deklarieren long k;und fügen Sie dies Lin der ersten Schleife hinzu k<1L<<N).

Karl Napf
quelle
1
Benötigt C für> 32 Elemente das "L" -Literal auf dem *1*<<noder ist das nur eine C ++ - Sache?
Mark Johnson
@ MarkJohnson ja, ich denke, es würde erfordern.
Karl Napf
1

05AB1E , 8 Bytes

<Äæ¹æR+P

Probieren Sie es 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]
Magische Kraken-Urne
quelle
1

JavaScript (Firefox 30-57), 57 Byte

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

Gibt ein Array aller Wahrscheinlichkeiten zurück. Wenn Sie das Array von Ereignissen auch wollen, dann für 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]]

Wenn Sie die Ereignisse als Zeichenfolge zulassen, sind es nur 80 Byte:

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

Subtrahieren Sie 1/für jede Lösung zwei Bytes, wenn die Wahrscheinlichkeit niemals Null sein wird.

Neil
quelle
Wie würden Sie dies in einem <script></script>Block ausführen ? Ich habe Probleme damit, dass das erste "für" unerwartet ist?
Mark Johnson
@ MarkJohnson Solange Sie Firefox 30 oder höher verwenden, sollte es nur funktionieren.
Neil
0

Perl 6, 24 19 Bytes von Latin-1

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

Älterer Code:

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

Dies ist eine Funktion. Benutze es so:

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

bekommen:

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

Erklärung des älteren Codes:

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

Der neuere Code ist im Grunde derselbe, nur mit terserer Syntax:

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

Die Karte generiert ein Array voller anyKonstrukte, die sich zu größeren anyKonstrukten multiplizieren und das Problem auf übersichtliche Weise lösen, ohne dass eine Schleife erforderlich ist.

Nicht die kürzeste Sprache für das Programm, aber es ist eine sehr direkte Übersetzung des Problems.


quelle
0

Dyalog APL , 10 Bytes

Neue Lösung

Indexursprung unabhängig. Anonyme Funktion. Nimmt die Wahrscheinlichkeitsliste als Argument.

∘.×/⊢,¨1-⊢

∘.×/ Die kartesische Produktreduktion ist vorbei

die Argumentwerte

jeweils gepaart mit

1-⊢ die Komplementargumentwerte (lit. eins minus die Argumentwerte)

TryAPL online!


Alte Lösung

Benötigt, ⎕IO←0was auf vielen Systemen Standard ist. Fordert zur Eingabe der Wahrscheinlichkeiten auf.

|⎕∘.×.-⊂⍳2

Erläuterung

| absoluter Wert von

die Eingabe, ɑ = [ ɑ ₁  ɑ ₂  ɑ ₃]

∘.×.-modifizierten inneren tensor multipliziert ( ɑ ₁ - B ₁) ⊗ ( ɑ ₂ - B ₂) ⊗ ( ɑ ₃ - b ₃), mit

⊂⍳2die beiliegende Liste b = [[0 1]]

Mathematische Definition

Als ɑ b eingeschlossen ist, ist es Skalar, und daher auf die Länge des erweiterten ɑ , nämlich 3, so dass der gesamte Ausdruck ist

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!

Hinweise (gilt sowohl für alte als auch für neue Lösung)

Das Programm und die Formel funktionieren für eine beliebige Anzahl ( n ) von Variablen und geben in jeder Dimension ein n- dimensionales Array der Länge 2 zurück. Bei drei Variablen ist die Wahrscheinlichkeit eines bestimmten Ergebnisses
P ( p , q , r ) = A p , q , r,
das bequem aus dem Array mit (⊃A)[p;q;r]extrahiert werden kannp q r⌷⊃A

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

Adam
quelle
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);

Laufen Sie wie folgt:

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

Beachten Sie, dass die Ausgabe Little Endian ist:

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

Erläuterung

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)

Optimierungen

  • 8 Bytes gespart, indem Binärlogik verwendet wurde, um das Bit abzurufen, anstatt es in einen String umzuwandeln
  • Ein Byte wurde gespeichert, indem das Zurücksetzen $pauf 1 mit der Berechnung von kombiniert wurde$c
  • Sie haben ein Byte gespeichert, indem Sie das Ergebnis von print (1) zu addieren, $ianstatt es zu erhöhen
  • Ein Byte wurde gespeichert, indem ein Unterstrich als Ausgabetrennzeichen verwendet wurde
  • Ein Byte mit dem Minuszeichen als Begrenzer gespeichert (es gibt keine negativen Chancen).
  • 6 Bytes gespart durch Verwendung von $canstelle von$$i
aross
quelle
0

C ++ 17, 137 131 129 Bytes

Speichern von 6 Bytes durch Festlegen #define A auto, dass ein so kurzes Makro zum ersten Mal etwas speichert. -2 Bytes für die Verwendung #importund das Löschen des Speicherplatzes vor<

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

Erzeugt alle möglichen Kombinationen.

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

Verwendung:

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