Randomely Erstellen einer booleschen Funktion von N booleschen Variablen

Ich möchte ein Programm zum randomely Erstellen einer Funktion schreiben, die als eine Eingabe N Binärwerte empfängt und sie auf einen Binärwert abbildet. Der naive Ansatz wäre, alle 2^(2^N) solchen Funktionen zu erzeugen, die als Wahrheitstabellen dargestellt werden, und eine zufällig zu wählen - aber dies ist für große N unpraktisch. Außerdem ist die Tabelle in der Wahrheit Speicher Ineffizient wäre es wünschenswert, es als eine Formel y = f (x1, x2, ..., xN) darzustellen.Randomely Erstellen einer booleschen Funktion von N booleschen Variablen

Danke!

Quelle

2016-09-17 user1767774

Angenommen, wir haben ein Array x[1..n] der Booleschen Werte. Die Idee ist, eine Hilfs-Bernoulli-Verteilung b zu erstellen und and oder or nacheinander mit einer Wahrscheinlichkeit von 50% anzuwenden.

1. result:= true. 
    b := Bernoulli(0.5). 
2. For i = 1 To n Do: 
3. If next(b) 
     Then result := and(result, x[i]) 
     Else result := or(result, x[i]) 
4. Return result

Quelle

2016-09-17 19:34:09

Vielen Dank! Aber wenn ich Ihre Lösung richtig verstanden habe, erstellen Sie eine zufällige Ad-hoc-Zuordnung der Eingabe zu einem booleschen Ergebnis. Ich möchte die Funktion zufällig aus allen möglichen Funktionen auswählen (wenn zum Beispiel N = 3 ist, kann eine mögliche gewählte Funktion f (x1, x2, x3) = x1 und (x2 oder x3) sein, eine andere kann f sein (x, 1, x2, x3) = (x1 oder x2) und x3), aber sobald es ausgewählt wurde, möchte ich die gleiche Funktion für verschiedene Eingaben verwenden können. – user1767774

@ user1767774 OK. Eine Idee könnte darin bestehen, zuerst die Folge von "oder" und "und" Operationen nach dem Zufallsprinzip zu erzeugen und sie dann auf beliebige andere Eingaben anzuwenden. –

Randomely Erstellen einer booleschen Funktion von N booleschen Variablen

Antwort

Verwandte Themen