Boolsche Warheitstafel Funktion gesucht....

Spacekiss · Samstag 9. Juli 2005, 00:12

Hallo,

ich habe ein Problem, bis jetzt ist mir bei vielen Problemen immer eine Idee gekommen, aber bei dem folgenden Fall hab ich selbst nach 3 Tage Kopfzerbrechen keine Lösung gefunden

Es soll folgendes gemacht werden, ich habe vorliegen eine Liste mit Variablen, z.B ["a", "b", "c"], nun möchte ich diese mit boolschen Werten kombinieren zu einer Wahrheitstafel mit allen möglichen Kombinationen. Da ich hier ja 3 Variablen habe ergibt das genau 8 Möglichkeiten:

["a",False] ["b",False] ["c", False]
["a",False] ["b",False] ["c", True]
["a",False] ["b",True] ["c", False]
["a",False] ["b",True] ["c", True]
["a",True] ["b",False] ["c", False]
["a",True] ["b",False] ["c", True]
["a",True] ["b",True] ["c", False]
["a",True] ["b",True] ["c", True]

und hier liegt das Problem, wie kann ich aus einer EIngabeliste mit Variablen, so eine Ergebnisliste erstellen...

für Ideen wär ich wirklich dankbar, danke im voraus...

Thorsten

jens · Samstag 9. Juli 2005, 09:23

Ich kann evtl. einen Denkanstoß geben... Die True-False-Matrix erinnert mich irgendwie an die Nullen und Einsen einer Binär-Tabelle...
Ich weiß zwar jetzt nicht, wie man an die Binär-Tabelle rankommt, aber bestimmt könnte man irgendwie die Breite festlegen und die Tabelle, mit deinen Daten verknüpfen. Also eine Binär-Tabelle mit einer Breite von vier sieht so aus s. BCD-Code:

Code: Alles auswählen

Leonidas · Samstag 9. Juli 2005, 09:59

Mich erinnert das eher an eine Art Permutation.. aber mir fällt jetzt grad auf die schnelle kein Lösungsweg ein.

Leonidas · Samstag 9. Juli 2005, 10:39

Okay, ich habe die so ziemlich schlechteste Lösung gefunden. Die Permutationsfunktion ist etwas buggy (ist nicht von mir, ich hatte keine Lust eine Permutationsfunktion selbst zu machen), so dass sie einige kombinationen mehrfach ausspukt, deswegen habe ich v2simple unw eingeführt.

Code: Alles auswählen

# Modified permutator by Hugh Brown

def xcomb(items):
    "Generator for permuting items in a list."
    if len(items) == 0: 
        yield []
    else:
        for i in xrange(len(items)):
            for cc in xcomb(items[:i] + items[i+1:]):
                yield [items[i]] + cc

def perm(items):
    "Return all permutations of items in a list."
    return list(xcomb(items))

valarray = [True, True, True]
v1 = perm(valarray)
v1simple = []
for value in v1:
    if value not in v1simple:
        v1simple.append(value)

valarray = [True, True, False]
v2 = perm(valarray)
v2simple = []
for value in v2:
    if value not in v2simple:
        v2simple.append(value)

valarray = [True, False, False]
v3 = perm(valarray)
v3simple = []
for value in v3:
    if value not in v3simple:
        v3simple.append(value)

valarray = [False, False, False]
v4 = perm(valarray)
v4simple = []
for value in v4:
    if value not in v4simple:
        v4simple.append(value)

vals = []
vals.extend(v1simple)
vals.extend(v2simple)
vals.extend(v3simple)
vals.extend(v4simple)

varset = []

for variation in vals:
    varset.append([['a', variation[0]], ['b', variation[1]], ['c', variation[2]]])

for variation in varset:
    print variation

Es sei mir zugute gehalten, dass ich gerade mal eine Stunde wach bin

Spacekiss · Samstag 9. Juli 2005, 12:03

hmmm hatte die Nacht auch noch dran gearbeitet und so eine ähnliche Lüsung gefunden, Problem ist ja weiterhin das ich das ganze dynamisch programmieren muss, also es nicht auf 3 Variablen beschränkt sein soll und dieser Schritt ist ziemlich übel

jens · Samstag 9. Juli 2005, 12:26

Was ist mit meiner Binär-Tabellen-Idee?
Dabei dürfte die Anzahl der Variablen egal sein...

Weiß jemand wie man in Python an den Binär-Code eines Zeichen herran kommt?

antimicro · Samstag 9. Juli 2005, 22:42

Spacekiss hat geschrieben: und hier liegt das Problem, wie kann ich aus einer EIngabeliste mit Variablen, so eine Ergebnisliste erstellen...

Hi,
irgendwie check ich dein Problem nicht wirklich

, aber soweit ich das verstanden habe musst du alle möglichen Kombinationen kennen. Das ist kein Problem wenn man die Anzahl der Variablen kennt und weiß das es sich um bool’sche Variablen handelt.
Oder möchtest du nur eine ganz normale Wahrheitstabelle für n Variablen bauen?

Spacekiss · Samstag 9. Juli 2005, 23:12

Naja mein Problem ist, dass es mit Sicherheit ne rekursive Funktion gibt die das im Handumdrehn macht und diese versuch ich die ganze Zeit zu erstellen, hab auch schon versucht dies über Binärbäume zu lösen nur dann gibts ab 4 Variablen derbe Probleme....

Naja und wenn such ich halt ne Funktion die eine Liste als Eingabe nimmt und eine Liste mit Wahrheitslisten ausgibt...

gerold · Sonntag 10. Juli 2005, 00:38

Spacekiss hat geschrieben: Es soll folgendes gemacht werden, ich habe vorliegen eine Liste mit Variablen, z.B ["a", "b", "c"], nun möchte ich diese mit boolschen Werten kombinieren zu einer Wahrheitstafel mit allen möglichen Kombinationen.

Hi Thorsten!

Ich glaube so sollte es funktionieren. Muss aber zugeben, dass ich jetzt fast zwei Stunden an diesem kurzen Programm gesessen bin.

Ich habe es der Einfachkeit halber mit 01-Strings probiert. Es sollte aber kein großes Problem mehr sein, diesen Prototypen in eine Liste, so wie du sie brauchst, umzusetzen.

Code: Alles auswählen

var_anz = 5
moeglichkeiten = 2 ** var_anz

liste = [""] * moeglichkeiten

bit = "0"
for i in range(var_anz):
   schalter = moeglichkeiten / (2 + i)
   for ii in range(moeglichkeiten):
      if i < (var_anz - 1):
         if not(ii % schalter):
            if bit == "0":
               bit = "1"
            else:
               bit = "0"
      else:
         if bit == "0":
            bit = "1"
         else:
            bit = "0"
      liste[ii] += bit

print "var_anz:", var_anz
print "moeglichkeiten:", moeglichkeiten
print "liste:", liste

mfg
Gerold

PS: Ich kann mir nur nicht vorstellen, für was man so etwas im wirklichen Leben brauchen könnte

BlackJack · Sonntag 10. Juli 2005, 01:51

gerold hat geschrieben:PS: Ich kann mir nur nicht vorstellen, für was man so etwas im wirklichen Leben brauchen könnte

Sind Hausaufgaben kein wirkliches Leben?

Ist mir ja fast ein wenig peinlich, das ich nur eine Minute hierfür brauchte:

Code: Alles auswählen

def bool_tab(variable_count):
    for i in xrange(2 ** variable_count):
        yield [bool(i & 2**bit) for bit in xrange(variable_count)]

print list(bool_tab(3))

gerold · Sonntag 10. Juli 2005, 10:05

BlackJack hat geschrieben: Ist mir ja fast ein wenig peinlich, das ich nur eine Minute hierfür brauchte:

Hi BlackJack!

Ätsch! Dafür ist meine Version länger als deine

lg
Gerold

Leonidas · Sonntag 10. Juli 2005, 10:29

gerold hat geschrieben:Ätsch! Dafür ist meine Version länger als deine

Pff.. meine Version ist sowohl länger als auch schrottiger als eure

Also wenn BlackJacks Lösung dem Python-Way nicht am nächesten kommt, dann weiß ich auch nicht mehr

tabellar · Sonntag 10. Juli 2005, 11:39

Super Thread,

es ist doch immer wieder erstaunlich, wieviel gute und weniger gute Programmierwege es für die gleiche Aufgabenstellung gibt

... und man sieht hier auch sehr deutlich, wie das gemeinsame Bearbeiten einer Aufgabe zu einer super Lösung führen kann

.

Tabellar

Spacekiss · Sonntag 10. Juli 2005, 18:07

Also Blackjacks Lösung ist

ärger mich garde das ich ent selber auf die Idee gekommen bin, naja bin eher Haskell gewöhnt, da sind for Schleifen unbekannt ^^

danke auf jeden Fall

Leonidas · Sonntag 10. Juli 2005, 18:13

Spacekiss hat geschrieben:naja bin eher Haskell gewöhnt, da sind for Schleifen unbekannt ^^

Ich versuche Haskell zu lernen, aber bin wohl zu doof in eine if..do Abfrage mehr als eine eine Anweisung zu schreiben.

Naja, gut, ich schweife ab. Dann wäre also das Thema erledigt.

BlackJack · Dienstag 12. Juli 2005, 22:25

Spacekiss hat geschrieben:Also Blackjacks Lösung ist ärger mich garde das ich ent selber auf die Idee gekommen bin, naja bin eher Haskell gewöhnt, da sind for Schleifen unbekannt ^^

Aber es gibt "List Comprehension" (LC). Die äussere ``for``-Schleife kann man auch noch durch eine ersetzen:

Code: Alles auswählen

def bool_tab(variable_count):
    return ([bool(i & 2**bit) for bit in xrange(variable_count)]
            for i in xrange(2**variable_count))

print list(bool_tab(3))

Eigentlich ist es eine "Generator Expression" wegen der runden Klammern statt der eckigen. Das ist der Python-Weg (ab Version 2.4) um "lazy evaluation" in LCs zu bringen.

In Haskell würde das so aussehen:

Code: Alles auswählen

import Bits

boolTab :: Int -> [[Bool]]
boolTab vars = [int2bools n vars    |  n <- [0 .. bit vars - 1]]
    -- Python: [int2bools(n, vars) for n in xrange(vars)]

int2bools :: Int -> Int -> [Bool]
int2bools n bits = [testBit n i|i <- [0 .. bits - 1]]

Ich habe die innere LC in eine Funktion rausgezogen und als Kommentar versucht die Übersetzung von LCs zwischen Haskell <-> Python deutlich zu machen.

@Leonidas: In Haskell gibt es keine "Anweisungen". Nur Funktionen. Und davon kann man nur in Ausnahmefällen mehrere nacheinander ausführen lassen, weil es streng genommen bei der Auswertung kein vorher/nachher gibt, weil keine Auswertereihenfolge vorgeschrieben ist. Das muss man natürlich für Ein-/Ausgabe Operationen machen können weil die "reale Welt" eben doch irgendwie sequentiell arbeitet.

``if`` habe ich in Haskell übrigens noch nie benutzt.

Leonidas · Dienstag 12. Juli 2005, 22:53

BlackJack hat geschrieben:@Leonidas: In Haskell gibt es keine "Anweisungen". Nur Funktionen.

Ich habe das Wort "Anweisung" stellvertretend für irgendeine Aktion des Programmes eingesetzt, diese Ungenauigkeit sei mir bitte verziehen.

BlackJack hat geschrieben:Und davon kann man nur in Ausnahmefällen mehrere nacheinander ausführen lassen, weil es streng genommen bei der Auswertung kein vorher/nachher gibt, weil keine Auswertereihenfolge vorgeschrieben ist. Das muss man natürlich für Ein-/Ausgabe Operationen machen können weil die "reale Welt" eben doch irgendwie sequentiell arbeitet.

Ja, ich denke das war eben genau so ein Fall (Monad), es ging zwar nicht um Dateien, aber die kommen später im Kapitel. Ich war nur recht deprimiert, dass das nicht so wollte wie ich.

BlackJack hat geschrieben:``if`` habe ich in Haskell übrigens noch nie
benutzt.

Da bin ich ja beruhigt, weil ifs unter Haskell sind wohl nicht mein Freund

wuf · Mittwoch 13. Juli 2005, 01:10

BlackJack hat geschrieben:Ist mir ja fast ein wenig peinlich, das ich nur eine Minute hierfür brauchte:

Hi BlackJack

Dein Zeitaufwand für die Lösung des Problems ist nicht
ganz ehrlich. Du hast vergessen die Zeit für das erst-
malige entdecken der Methode 'yield' die in einer Python
Dokumentation sicher nicht im ersten Kapitel zu finden ist,
und die Möglichkeiten der Methode zu erforschen, nicht
mit einberechnet Hi. Ich vermute da eher 5 Minuten.

Deine Lösungsansatz für das Problem ist aber genial!

Gruss wuf

HarryH · Mittwoch 13. Juli 2005, 06:28

Hallo,

Bin gerade auf eine Lösung Dookies zu obigen Problem gestoßen.
Dookies Lösung bietet aber noch mehr Anwendungsbereiche, da sie zu jedem Iteratorobjekt alle möglichen Kombinationen erstellt.

http://www.python-forum.de/viewtopic.php?t=1812

Leonidas · Mittwoch 13. Juli 2005, 08:21

wuf hat geschrieben:Du hast vergessen die Zeit für das erst-
malige entdecken der Methode 'yield' die in einer Python
Dokumentation sicher nicht im ersten Kapitel zu finden ist,
und die Möglichkeiten der Methode zu erforschen, nicht
mit einberechnet Hi. Ich vermute da eher 5 Minuten.

Ich vermute, dass das bei BlackJack schon ewig lange her ist, dass sich das nicht mehr rechner. Wenn du's mitrechnen willst, müsstest du ja auch noch die Zeit zum Python-lernen einrechnen und dann kommst du auf etwas mehr als 5 Minuten