Kombinatorik Algorithmus

Wissenschaft Mathematik
1

Hallo,

ich habe ein echt kniffeliges Problem. Gegeben seinen verschiedene Merkmale mit verschiedenen Ausprägungen:
Bsp.: Merkmal 1 hat die Ausprägungen 1,2,3
Merkmal 2 meinetwegen A,B,C und
Merkmal 3 X,Y,Z

Ebenfalls gegeben sind verschiedene Kombinationen:
Bsp: 1AY, 1AZ, 2AY, 2AZ

Ausgangspunkt für diese Kombinationen sind Formeln, die „ausmultipliziert“ wurden. Dabei sind die Merkmale untereinander UND-verknüpft und die Ausprägungen innerhalb der Merkmale ODER-verknüpft.
Bsp: (1 oder 2) und A und (Y oder Z)

Ich suche einen Algorithmus, der die Kombinationen wieder in die Formeln umwandelt. Problem an der Sache ist, dass auch Kombinationen verschiedener Formeln gegeben sind.

Bsp: 1AY, 1AZ, 2AY, 2AZ, 2BY, 2BZ aus den Formeln:
(1 oder 2) und A und (Y oder Z)
2 und B und (Y oder Z)

NICHT ist im Ergebnis nicht zulässig, kommt in den Kombinationen aber auch nicht vor. Das Ergebnis muss die Form ‚(a oder b) und (r oder s)‘ haben, also ODER-Verknüpfungen innerhalb der Merkmale und UND-Verknüpfungen zwischen den Merkmalen. Es ist nicht zwingend notwendig, dass es genau die Ausgangsformeln sind, aber die Anzahl der Formeln sollte möglichst gering sein. Zudem darf ein und dieselbe Kombination nicht als mögliches Ergebnis verschiedener Formeln auftauchen.

Ich habe es bereits mit Boolscher-Algebra versucht (deshalb auch die darstellung mit UND und ODER). Von Hand funktioniert es so auch einigermaßen (mit wenigen Merkmalen und Ausprägungen und ein wenig genauem Hinsehen), aber bei einer größeren Menge an gegebenen Kombinationen und Merkmalen wird es wirklich anstrengend.

Hintergrund ist, das beim Laden der Formeln in eine Datenbank diese aufgelöst und gespeichert wurden, und jetzt sollte ich die Formeln bestmöglich rekonstruieren.

Für ein bischen (oder auch viel :wink: ) Hilfe oder ein paar Denkanstöße wäre ich sehr dankbar.

Grüße
Benny

2

Hi Benny,

vllt hab ich das Problem nicht ganz begriffen, aber gegeben ist ein set von n-Tupeln der Form (a_i1, a_i2, a_i3,…,a_in), i=1,…,m.
Hierbei ist jedes ai ein Element einer Menge M_i={x_1, x_2, x_n_i}, wobei n_i eine natürliche Zahl (> 0) ist.
Es gibt also n Merkmale mit n_i Ausprägungen (i=1,…,n).

Wenn du schon weißt, dass alle Merkmale mit UND verknüpft sind und alle Ausprägnungen mit ODER und keine missings austreten können (d.h. jedes Tupel hat immer Länge n), dann ist doch der Schnitt über alle m Tupel an der Stelle i die Menge der Ausprägnungen von Merkmal i.

n gibt dir also die Anzahl der Merkmale vor, und n_i die Zahl der Ausprägungen, fertig.
Oder was hab ich übersehen?

Grüße,
JPL

3

Hallo,

erstmal danke für deine schnelle Antwort.

Wenn ich dass jetzt richtig verstehe, dann meinst du, dass ich mir einfach anschaue, was für Ausprägungen der einzelnen Merkmale vorhanden sind, und diese dann direkt in die Formel einsetze. Also:

für 1AY, 1AZ, 2AY, 2AZ -> Merkmal 1 hat „1“ und „2“ als Ausprägung
Merkmal 2 hat „A“
Merkmal 3 hat „Y“ und „Z“
-> (1 ODER 2) UND A UND (Y ODER Z)

Problem an der Sache ist, dass auch Tupel aus mehreren (vielen) Formeln zusammen auftreten können.

Bsp: 1AY, 1AZ, 2AY -> Merkmal 1 hat „1“ und „2“
-> Merkmal 2 hat „A“
-> Merkmal 3 hat „Y“ und „Z“
Wenn ich daraus jetzt die selbe Formel mache wie oben
[(1 ODER 2) UND A UND (Y ODER Z)], würde die Kombination 2AZ auch gültig, obwohl sie nicht angegeben war. Aus diesen drei Kombinationen kann man also entweder
[1 UND A UND (Y ODER Z)] und [2 UND A UND Y] oder
[(1 ODER 2) UND A UND Y] und [1 UND A UND Z] machen.

Und eben genau hier liegt mein Problem. Die „ausmultiplizierten“ Kombinationen so weit wie möglich vereinfachen aber ohne neue Kombinationen hinzuzufügen oder eine Kombination in zwei Formeln zu verwenden (also zwei Formeln dürfen nicht eine einzige gleiche Lösung haben). Ach ja, man könnte sagen, das ODER ist exklusiv, da die Merkmale immer nur eine Ausprägung zur gleichen Zeit annehmen können.

Mein Ansatz war, die Kombinationen, die sich am ähnlichsten sind, zusammenzufassen (also ausklammern mit dem Distributivgesetz). Aber das ist, wenn ich es programmiere, doch sehr inperformant.

Hoffe das Problem ist jetzt etwas klarer.

LG Benny

4

Hi Benny,

Wenn ich dass jetzt richtig verstehe, dann meinst du, dass ich
mir einfach anschaue, was für Ausprägungen der einzelnen
Merkmale vorhanden sind, und diese dann direkt in die Formel
einsetze. Also:

für 1AY, 1AZ, 2AY, 2AZ -> Merkmal 1 hat „1“ und „2“ als
Ausprägung
Merkmal 2 hat „A“
Merkmal 3 hat „Y“ und „Z“
-> (1 ODER 2) UND A UND (Y ODER Z)

Genau.

Problem an der Sache ist, dass auch Tupel aus mehreren
(vielen) Formeln zusammen auftreten können.

Bsp: 1AY, 1AZ, 2AY -> Merkmal 1 hat „1“ und „2“
-> Merkmal 2 hat „A“
-> Merkmal 3 hat „Y“ und „Z“
Wenn ich daraus jetzt die selbe Formel mache wie
oben
[(1 ODER 2) UND A UND (Y ODER Z)], würde die Kombination
2AZ auch gültig, obwohl sie nicht angegeben war.

Verstehe.

Das wird knifflig. Es gibt in deinem Bsp. eine Verbindung von 1 und 2 zu A und von A zu Z und Y. Mit dem obigen Verfahren ergibt sich dann auch eine Verbindung von 2 zu Z, eben die, die du nicht haben willst. Würde man diese aber als „unerlaubte“ Verbindung deklarieren, könnte man in einem 2-Schritt-Verfahren vorgehen:

  1. Formelbildung wie oben (es entstehen aber zu viele Kombinationen)
  2. Wirf alle Tupel wieder raus, für die gilt: 1.Merkmal = 1 UND 3.Merkmal = Z.
    Diese „unerlaubten“ Verbindungen könnte man herausbekommen, indem man alle Tupel aus 1. mit allen gegebenen vergleicht.

Zugegeben, ist keine elegante Lösung, vllt. fällt jemand anderem noch was Besseres ein.
Grüße,
JPL