Office: Beliebige Kombinationen von Elementen einer Menge (Permutationen) finden

Hallo,

gleich einmal vorweg: dieses Thema stellt die Fortsetzung einer (leider unsachlich gewordenen) Diskussion im Thema "Mehrere identische Daten innerhalb einer Zeile bewerten" dar. Aus Gründen der Übersichtlichkeit stelle ich das Thema "Permutationen" jetzt einmal getrennt dar.

Das Problem ist folgendes:

Mein Datensatz besteht aus n Zeilen, welche unterschiedliche Verschlüsselungen z.B. der Form 1-234.5y in m Spalten nebeneinander enthalten.

Hier ein Beispiel einer Zeile als Menge:

{5-123.4; 1-564.3y; 9-332.01}

Nun möchte ich alle Zeilen finden, welche Kombinationen der Elemente einer von mir vorgegebenen Menge darstellen. So etwas nennt man im mathematischen Sinne "Permutation", da es hierbei nur auf die Elemente selbst, nicht aber auf deren Reihenfolge innerhalb der Menge ankommt.

Etwas plastischer:

nähme ich o.g. Menge als Referenz, so müßten folgende Zeilen gefunden werden:

{5-123.4; 1-564.3y; 9-332.01}
{5-123.4; 9-332.01; 1-564.3y}
{9-332.01; 5-123.4; 1-564.3y}
{9-332.01; 1-564.3y; 5-123.4}
{1-564.3y; 5-123.4; 9-332.01}
{1-564.3y; 9-332.01; 5-123.4}

Das ergibt also - mathematisch in der Kombinatorik zu finden als "n über k", also "3 über 3" (s. Online-Hilfe zu Excel unter "VARIATIONEN") - gleich 6 Möglichkeiten, die Elemente der Menge zu kombinieren. Bei 5 Elementen ergibt das schon 120 Möglichkeiten, was also einen erheblichen Aufwand ergibt, wenn man dies manuell versucht.

Mein Ziel ist nun folgendes:

in einem Extra-Tabellenblatt gebe ich die Elemente wahlweise in einer Zeile vor (Reihenfolge spielt ja keine Rolle) - wir nehmen der Einfachheit halber einmal eine aufsteigend sortierte Reihenfolge, also z.B. auf o.g. Menge bezogen

{1-564.3y; 5-123.4; 9-332.01}

Nun füge ich an alle Zeilen meines Datensatzes eine Spalte an, welche die (von mir gesuchte) Formel zum Finden von Permutationen der vorgegeben Menge enthält, mit einem Bezug zu dem Tabellenblatt, wo die zu untersuchende Menge steht.

Ist die zu untersuchende Zelle eine Permutation, so soll die Formel WAHR ergeben, sonst FALSCH. So könnte ich dann am Ende einfach alle Permutationen mit dem Autofilter herausfiltern, indem ich in der Spalte nur den Wert WAHR anzeigen lasse. Das wirklich Interessante ergibt sich dann in den anderen Spalten des Datensatzes, welche mit den Verschlüsselungen zusammenhängen (so etwas wie Datum, Ort o.ä.).

Johannes alias JFREUDENS hat bereits eine Möglichkeit gefunden, wie man Permutationen von Mengen herausfinden kann (siehe o.g. Thema), welche allerdings als Elemente nur Zahlen darstellen und keine Lücken aufweisen dürfen...

... und genau da liegt der Knackepunkt: es gibt eine große Anzahl von den zu untersuchenden Verschlüsselungen, so dass eine "Verschlüsselung der Verschlüsselung" (indem ich die Verschlüsselung einfach durch eine Transformation in Zahlen umwandle) das ganze wieder komplizierter, aufwendiger und unübersichtlicher macht. Außerdem tauchen sehr wohl Lücken auf.

Ich habe folgende Formel versucht (Matrixformel):

{UND(NICHT(ISTNV(SVERWEIS(ANFANGSSPALTE:ENDSPALTE;$A$1000:$C$1000;1:3;FALSCH)))) },

sprachlich:

"Wenn nicht alle Elemente gleichzeitig (UND) in der zu untersuchenden Menge vorkommen, dann gib FALSCH aus, sonst WAHR."

wobei


ANFANGSSPALTE:ENDSPALTE die zu untersuchenden Spaltenkoordinaten der zu untersuchenden Zeile darstellen,

$A$1000:$C$1000 die zu untersuchende Menge enthält,

1:3 bedeutet, das SVERWEIS alle Spalten durchgehen soll,

FALSCH bedeutet, es soll nur GENAU der Wert gefunden werden.


Das Problem:
die obige Formel untersucht NUR DIE ERSTE Spalte, ob diese in der Menge vorkommt. Alle anderen Spalten bleiben unberücksichigt. Des weiteren - um bei der Beispielmenge zu bleiben - würde sicherlich auch

{5-123.4; 1-564.3y; 1-564.3y; 9-332.01}

gefunden werden... aber für Doppelzählungen innerhalb einer Zeile wurde ja auch schon eine Lösung gefunden (s. Beitrag von Hajo alias Hajo_Zi im o.g. Thema). *biggrin.gif*

Das Problem, dass nur die erste Spalte untersucht wird, ergibt sich auch mit anderen Funktionen, wie z.B. VERGLEICH, IDENTISCH... es sieht so aus, als könne man eine Formel, in der eine Matrix auftaucht, nicht noch einmal in eine (geschweifte) Matrix-Formel umwandeln....?!

So, Johannes, ich hoffe, ich habe meine Frage allgemein verständlich und detailliert beschrieben und gezeigt, dass ich mir sehr wohl selber Gedanken mache und nicht nur andere für mich arbeiten lasse. *biggrinlove

Viele liebe Grüße!
Marco

:)

 

Hallo Marco,

das sind jetzt wirklich viel mehr und viel bessere Informationen. In dem abgeschlossenen Thread war leider nie die Rede von Buchstaben. Sei's drum: Neues Spiel, neues Glück und ich werde gerne weiter versuchen, Dir zu helfen.

Hier ein Vorschlag, wie Du das Problem lösen kannst.
Aufbau: Suchmatrix in Tabelle3!A1:C1
Zu durchsuchende Matrix: Tabelle2!A1:P1000

Die Zeilen in Tabelle2, die eine Permutation der Elemente aus Tabelle3 enthalten, identifizierst Du durch folgende Formel:

{=UND(NICHT(ISTNV(VERGLEICH(Tabelle3!A$1:C$1;Tabelle2!A1:P1;0))))}

Diese Formel in eine freie Zelle in Zeile 1 eingeben und dann runterkopieren.

Und dann noch ein kleiner Hinweis. Wenn ich mich richtig an meine Schulzeit erinnere, berechnet man die Zahl der möglichen Permutationen nicht mit "n über k", sondern mit Fakultät(n). "n über k" sind doch die Binomialkoeffizienten, also die Anzahl der Kombinationen mit k Elementen aus n Elementen ohne Berücksichtigung der Reihenfolge. Dein Beispiel 3 über 3 ist auch nicht 6, sondern 1.

CU

Johannes

 

Hallo Johannes,

ups, da hat mich einer erwischt... und dabei habe ich versucht, mich so mathematisch korrekt wie möglich auszudrücken... daran hat Excel Schuld, die Online-Hilfe hat mich auf den falschen Weg geführt! *biggrin.gif*

In der Tat berechnet man die Möglichkeiten OHNE Berücksichtigung der Reihenfolge mit "n über k", die Binomialkoeffizienten. Dann ergibt natürlich "3 über 3" in der Tat 1, da ich drei Elemente aus einer Menge von drei Elementen ja nach Abzug der möglichen Reihenfolgen (also bspw. sortiert) nur einmal "ziehen" kann... also, das ist jetzt auch mißverständlich, oder? Auf jeden Fall kam mir die 6 (bzw. 120) schon sehr merkwürdig vor, und mir schwante Böses... ich habe in Erinnerung, dass die Binomialkoeffizienten symmetrisch sind (also "3 über 1" ist das selbe wie "3 über 3")...

Auf jeden Fall habe ich statt KOMBINATIONEN in Excel VARIATIONEN gefunden (warum schickt mich die Online-Hilfe nicht gleich zu KOMBINATIONEN???).

Bei Fakultät müßte dann eigentlich das gleiche rauskommen wie bei KOMBINATIONEN, oder? Bei 5 Versuchen bleiben nach dem ersten Ziehen noch 4, dann 3, dann 2 und dann 1 Element übrig, also 5x4x3x2x1 = 5! = 120 Möglichkeiten unter Berücksichtigung der Reihenfolge, nicht? Oder sind KOMBINATIONEN auch wieder was anderes?!? Werden da etwa gleiche Elemente rausgerechnet? Heidewitzka, ist das kompliziert... also, irgendwie bin ich zu lange raus aus der Materie... außerdem war das mit der Kombinatorik - glaube ich - auch nie meine Stärke. *bawling

Also, vielen Dank für die Formel. Ich probiere sie möglichst bald aus - so weit es die Arbeit zuläßt - und melde mich dann.

CU
Marco

 

Hallo Marco,

mit der Erklärung von n über k haben wir beide daneben gegriffen. n über k liefert die Zahl der möglichen k-Tupel aus n verschiedenen Elementen unter Berücksichtigung der (inneren) Reihenfolge und ohne Zurücklegen.

Beispiel: 3 über 2 liefert die Zahl der möglichen Zweierkombinationen aus drei verschiedenen Elementen. Aus a, b, und c lässt sich ab, ac, ba, bc , ca und cb ziehen.

Die Aussage zur Symmetrie der Binomialkoeffizienten stimmt. Fast. Denn 3 über 3 ist nicht gleich 3 über 1, sondern gleich 3 über 0. Und das ist tatsächlich 1. Die Koeffizientenreihe ist 1, 3, 3, 1.

Die Sache mit Kombinationen und Variationen in Excel verhält sich folgendermaßen: Kombinationen ist z. B. das Lottospiel. Die Reihenfolge, in der du die Kreuzchen gemacht hast, muss nicht mit der Reihenfolge der Ziehung übereinstimmen.

Bei den Variationen müssen auch noch beide Reihenfolgen gleich sein. Deshalb gibt es k! mehr Variationen als Kombinationen.

Ich hoffe, ich hab's nicht wieder verwechselt.

Ciao

Johannes

 

Hallo Johannes,

ja, jetzt dämmert's mir wieder so langsam...

Wie viel man doch im Laufe der Zeit vergißt... *bawling

Aber:

Du sagst, "n über k" berücksichtigt die (innere) Reihenfolge... ich habe - glaube ich - in der Schule gelernt, dass beim Lottospielen "49 über 6" bedeutet, wie viele Möglichkeiten es gibt, sechs Richtige zu ziehen...
ah... jetzt habe ich's... mit der 6 sind dann beliebige Zahlen gemeint, stimmt's? Also alle Möglichkeiten, OHNE Berücksichtigung der Reihenfolge 6 aus 49 unterschiedlichen Zahlen zu ziehen...

Die Binomialkoeffizienten sind doch z.B. gleich "3 über 2" gleich 3...
bei 3 verschiedenen Elementen gibt es folgende Möglichkeiten, 2 zu ziehen (wie Du schon gezeigt hast):


ab, ba, ac, ca, bc, cb


Das sind aber die Permutationen (also 3!=6 Möglichkeiten)!

Lasse ich die Reihenfolge unberücksichtigt, dann gibt es 3 Möglichkeiten:


ab (gleich ba); ac (gleich ca) und bc (gleich cb)


Und das wiederum entspricht "3 über 2" gleich 3 Möglichkeiten.


In der Excel-Online-Hilfe heißt es unter VARIATIONEN:

"Liefert die Anzahl der Möglichkeiten, um k Elemente aus einer Menge von n Elementen ohne Zurücklegen zu ziehen. Eine Variation ist eine Kombination ohne Wiederholung, deren interne Anordnung oder Reihenfolge zu berücksichtigen ist (z.B. Pferdewetten). Variationen unterscheiden sich von Kombinationen, deren interne Anordnung unberücksichtigt bleibt (z.B. Zahlen-Lotto 6 aus 49)."


Schau mal hier:
http://members.aol.com/mathfuzzy/THE.../kombinat.html


??? Werde ich jetzt langsam verrückt ??? *tongue.gif*

Egal, werde bei Zeiten mal wieder meine Formelsammlung rausholen müssen...

CU
Marco

 

Hallo Johannes,

ich habe Deine Formel einmal ausprobiert, und sie funktioniert wunderbar, so lange man keine leeren Zellen hat.

	A	B	C	D	E
1	zu suchende Zeichenfolge (ohne Leerzellen):
2	a	b	c	ERGEBNIS
3	c	a	b	WAHR

[/quote]

D3 : {=UND(NICHT(ISTNV(VERGLEICH(A:$C;A3:C3;0))))}

Leider funktioniert es schon nicht mehr, wenn Leerzellen vorkommen.

	A	B	C	D	E	F
5	zu suchende Zeichenfolge (mit Leerzellen):
6	a	b	c			ERGEBNIS
7		a	b	c		FALSCH
8	b	a	c			FALSCH
9			c	b	a	FALSCH

[/quote]

F7 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A7:E7;0))))}
F8 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A8:E8;0))))}
F9 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A9:E9;0))))}

Ein Workaround wäre, die Leerzellen mit einer Zeichenfolge zu füllen, welche sonst nicht im Datensatz vorkommt.

	A	B	C	D	E	F
11	zu suchende Zeichenfolge (mit xxx anstatt leer):
12	a	b	c	xxx	xxx	ERGEBNIS
13	xxx	a	b	c	xxx	WAHR
14	b	a	c	xxx	xxx	WAHR
15	xxx	xxx	c	b	a	WAHR

[/quote]

F13 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A13:E13;0))))}
F14 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A14:E14;0))))}
F15 : {=UND(NICHT(ISTNV(VERGLEICH($A:$E;A15:E15;0))))}

Kennst Du vielleicht eine Möglichkeit, dies in die Formel einzubauen?


(Alle Tabellenwebansichten erstellt mit

 

Hallo Marco,

kannst du mal hier eintragen,
wie denn die Ergebnisse aussehen sollten:

	A	B	C	D	E	F	G
1						Ergebnis soll sein Matrix 1?	Ergebnis soll sein Matrix 2?
2	Suche1:		a	bc	c
3	Suche2:		g		e
4	Suche3:		bc	c
5
6	Matrix 1		g	e	a
7			bc	g	e
8			bc	a	c
9
10	Matrix 2		e	g
11			bc		c
12			bc	a

[/quote]
Tabellenwebansicht erstellt mit

 

Hallo Marco,

du wolltest doch bislang auch gar nicht nach Permutationen von leeren Zellen suchen, sondern hattest typische Suchmuster vogegeben.

Wenn Du in meiner Formel den ersten Bereich so angibst, dass dort auch das steht was du wirklich suchst, funktioniert es selbst dann, wenn Leerzellen in der zu durchsuchenden Matrix vorkommen.

{=UND(NICHT(ISTNV(VERGLEICH($A$6:$C$6 ;A7:E7;0))))}

Die zu durchsuchenden Zeilen müssen nicht gleich viele Spalten haben wir die Suchmatrix!

Meine Formel hat übrigens doch noch eine Eischränkung: In der Suchmatrix dürfen keine doppelten Werte stehen. Eine Zeile würde auch dann als Permutation erkannt, wenn in der fraglichen Zeile der entsprechende Eintrag nur einmal gefunden wird.

Aber auch das war zumindest bislang nicht gefragt.

@Peter: Mit diesen Vorgaben macht nur die Suche1 Sinn. Nur Zeile 8 dürfte als Permutation erkannt werden.

Ciao

Johannes

 

Hallo,

ich habe eine Möglichkeit gefunden, bei den Permutationen Doppelnennungen auszuschließen, indem ich die Formeln von Johannes für Permutationen und Doppelnennungen nutze (letztere habe ich dahingehend modifiziert, dass generell keine Leer- oder Nullerzellen berücksichtigt werden).

Anmerkungen:

$A42:$C$42 Vergleichsmatrix (Zeile)
A43:E43 Suchmatrix (Zeile)


1. Prüfen, ob eine Permutation vorliegt (aber: Problem Doppelnennungen)

={UND(NICHT(ISTNV(VERGLEICH($A$42:$C$42;A43:E43;0))))}


2. Prüfen auf Doppelnennungen (modifiziert):

={WENN(UND(MAX(ZÄHLENWENN(A43:E43;WENN(ODER(NICHT(ISTLEER(A43:E43));A43:E430);A43:E43;"")))>1;ODER(NICHT(ISTLEER(A43:E43));A43:E43""));WAHR;FALSCH)}


3. Prüfung auf beides (kombiniert):

={UND(F43;NICHT(G43))}

wobei F43 exemplarisch für 1. und G43 exemplarisch für 2. steht.



Das Ergebnis sieht folgendermaßen aus:

	A	B	C	D	E	F	G	H
37	zu suchende Zeichenfolge
38	a	b	c			Permutation?	Doppelt?	F43 UND NICHT G43?
39		a	b	c		WAHR	FALSCH	WAHR
40	b	a	c			WAHR	FALSCH	WAHR
41	c	b	c	b	a	WAHR	WAHR	FALSCH
42	a	a	b	b	c	WAHR	WAHR	FALSCH
43	a	b	d	d	c	WAHR	WAHR	FALSCH
44		d	d	a	c	FALSCH	WAHR	FALSCH

[/quote]
Tabellenwebansicht erstellt mit

 

... da fällt mir gerade noch etwas auf...

In Zeile 43 sind 2 d's mit reingerutscht und werden nach der Formel dennoch als Permutation anerkannt...

Wie kann ich das nun so anpassen, dass die Zeile nicht als Permutation gesehen wird (weil d nicht in der Vergleichsmatrix vorkommt)?

Gruß
Marco