Live-Forum - Die aktuellen Beiträge
Anzeige
Archiv - Navigation
1396to1400
Aktuelles Verzeichnis
Verzeichnis Index
Übersicht Verzeichnisse
Vorheriger Thread
Rückwärts Blättern
Nächster Thread
Vorwärts blättern
Anzeige
HERBERS
Excel-Forum (Archiv)
20+ Jahre Excel-Kompetenz: Von Anwendern, für Anwender
Inhaltsverzeichnis

Knobelaufgabe Kombinatorik:Reihen-/Spaltenvergleic

Knobelaufgabe Kombinatorik:Reihen-/Spaltenvergleic
25.12.2014 23:18:04
Joerschi
Knobelaufgabe Kombinatorik: Reihen-/Spaltenvergleich, "Masterreihe" finden
Hallo liebes Forum,
ich möchte folgendes Kombinatorik(?)problem lösen, komme aber überhaupt nicht weiter bzw. finde keinen Ansatz.
Die Erklärung anhand einer Skizze, weil somit leicht verständlich.
Userbild
(farbliche Unterscheidung nur für den besseren Überblick)
Musterdatei dazu: https://www.herber.de/bbs/user/94586.xlsx
Ausgangslage:
Es gibt jeweils x Anzahl an Reihen zeilenweise (max. 50, hier im Bsp. 17) und 13 Positionen spaltenweise.
Die höchste Zahl je Zelle ist jeweils 3, die niedrigste 1.
Jede Reihe hat eine Gesamtsumme (alle Zahlen von Position 1 bis 13 summiert).
Verglichen werden untereinander zuerst die Positionen aller Reihen, danach die Reihen selbst.
Ich möchte nun eine selbst erstellte "Masterreihe" finden (gelbe Markierung), welche möglichst viele Reihen der Tabelle abbildet.
Dabei gilt zu beachten: Die höhere Zahl einer bestimmten Position "toppt" eine niedrigere Zahl dergleichen Position (3 toppt 2 und 1; 2 toppt 1; 1 ist gleichwertig 1).
"Toppt" bedeutet, die Bedingung ist immer erfüllt, wenn die gleiche oder eine höhere Zahl auf der gleichen Position der Masterreihe (gegenüber der Position jeder Reihe in der Tabelle) vorhanden ist.
Theoretisch müsste es also immer eine Lösung geben, wenn jede Position = 3 ist.
Zusammengefasst:
Ziel ist eine Masterreihe für Pos. 1-13 zu finden, welche die beiden nachfolgenden, gegensätzlichen Bedingungen
erfüllt:
Hauptbedingung A) Möglichst viele der Reihen sollen durch die Masterreihe abgedeckt werden
Nebenbedingung B) die maximale Summe der Reihe muss eingehalten werden (= manuelle Vorgabe)
Auf der einen Seite muss also die Summe aller Zahlen je Reihe unter der manuell gesetzten Bedingung sein (B)), auf der anderen Seite sollen so viele Reihen wie möglich die Masterreihe erfüllen (A)).
Also zwei gegensätzlich verlaufende Faktoren für eine Lösung, welche imo nur eine PC-Lösung schaffen kann.
Ehrlich gesagt habe ich keine Ahnung, ob die "Aufgabe" überhaupt und mit Excel/VBA lösbar ist, mir selbst fehlt auch die mathematische Idee (falls es eine solche bei der Problemstellung überhaupt gibt).
Aber falls jemand eine praktikable Idee hat, ist er sich meines zutiefst empfundenen Dankes gewiss :-)).
PS Zusatz: Falls es möglich ist, manuell noch die maximale Anzahl der Einser je Reihe festzulegen (als Vorbedingung), wäre das perfekt. Verkompliziert den Algho aber wahrscheinlich.
Viele Grüße und Merry Christmas
Joerschi

9
Beiträge zum Forumthread
Beiträge zu diesem Forumthread

Betreff
Datum
Anwender
Anzeige
AW: Knobelaufgabe Kombinatorik:Reihen-/Spaltenvergleic
26.12.2014 00:20:49
Matthias
Hallo Joerschi
Ich habs jetzt mehrmal gelesen und verstehe "nur Bahnhof"
Evtl. kannst Du es noch mal etwas anders beschreiben.
Hier sind jetzt mal per Zufall erzeugte Werte von 1 bis 3 je Zelle
 ABCDEFGHIJKLMNO
11Reihe 8323321311323330
12Reihe 9333133112322330
15Reihe 12332313232331130
18Reihe 15212223222333330


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4
Ich habe eine Schleife laufen lassen bis im Bsp. 4x die 30 als Summe erscheint.
Im Bsp. habe ich nun nach Summe gefiltert.
Was aber nun mit den Daten passieren soll, habe ich noch nicht so recht verstanden. (Sorry)
Kannst Du es bitte nochmal anders erklären?
Gruß Matthias

Anzeige
noch ein 2.Beispiel ...
26.12.2014 00:31:42
Matthias
Hallo
Hier mit 6x der Summe(30)
 ABCDEFGHIJKLMNO
4Reihe 1213331233233130
8Reihe 5221123333322330
13Reihe 10222131333313330
14Reihe 11323133323131230
17Reihe 14322223223233130
19Reihe 16321233331132330


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4
Welche Daten willst Du nun hier miteinander vergleichen?
Was soll jetzt die Masterreihe sein?
Wie bereits geschrieben, ich habs noch nicht verstanden.
Gruß Matthias

Anzeige
...bisschen anders/ergänzend erklärt
26.12.2014 09:13:00
Joerschi
Hi Mathias,
Danke Dir erstmal für das Engagement.
Hmmm... Schwer zu beschreiben.
Die Masterreihe (MR) soll sozusagen "neu erschaffen" werden und möglichst viele Reihen mit ihren Werten enthalten/abdecken. Die WErte der MR sollen dabei an ihrer jeweiligen Position größer oder gleich sein als der jeweilige Positionswert in den Tabellen-Reihen der Basistabelle.
Vielleicht mal nur an einer Reihe als Beispiel, dann versteht man es bestimmt leichter:
Userbild
Musterdatei neu: https://www.herber.de/bbs/user/94588.xlsx
Die MR1 und MR2 ist manuell willkürlich gewählt (soll ja errechnet werden). Unter der Reihe 2 habe ich ja/nein eingepflegt, ob die Bedingung erfüllt ist (Zahlenwert Masterreihe größergleich jeweiliger Wert der Reihe).
Bei MR1 sieht man schön, dass oft nicht erfüllt ist (Wenn auch nur einmal ein "n" erscheint, wird die Reihe nicht von der MR abgedeckt).
Bei MR2 würde jeder Wert erfüllt werden.
Es ist natürlich grundsätzlich so, dass - je höher man die Summenanzahl setzt - bzw. wenn man ganz oft die 3 in der MR hat, umso mehr Reihen erfüllt werden (weil die 3 als höchste Zahl immer alles abdeckt und immer die Bedingung erfüllt).
Die Kunst in der rechnerischen Suche der MR wäre jetzt, dass
a) gleichzeitig die Summenanzahl erfüllt ist und die MR gleichzeitig unbedingt so viele Reihen als möglich aus der Tabelle abdeckt (also wo man kein einziges "n" im direkten Vergleich der Positionen hinschreiben müsste).
Deswegen meinte ich, man muss wahrscheinlich (?) erst sowohl die Positionen der MR mit jeder Reihe vergleichen und dann auf wie viele Reihen das überhaupt zutrifft.
Ich habe halt keinen Ansatz, wie man eine clevere MR erschafft. Ob durch "Probieren" (alle denkbaren MR mit vorgeg. Summenanzahl erschaffen) und dann nacheinander prüfen, dass möglichst viele Reihen da reinpassen oder durch systematisches Aufbauen der MR von Position um Position.
Ich bin mir jedoch bewusst, dass es nicht immer eine Lösung geben wird. Besonders wenn man die Summenanzahl nach unten schraubt, kann es wahrscheinlich schnell keine MR mehr geben (außer man übernimmt einfach direkt eine der Reihen mit ihren Werten, wobei dann wahrscheinlich auch nur diese eine Reihe erfüllt wäre).
Wenn es den Rechenaufwand einschränken soll, können wir als Fixpunkte der MR gern eine 1 in Position 1 und 2 vorgegeben (ist also in jeder MR enthalten; es werden nur die Pos. 3 - 13 "erschaffen"). Würde später eh so werden.
Besser erklärt? *bisschenpeinlichguck* :-))
LG; Joerschi

Anzeige
AW: ...bisschen anders/ergänzend erklärt
26.12.2014 15:06:30
Matthias
Hallo
Du meinst es so ?
z.B. für Reihe1 mehrere/alle unterschiedl. Masterreihen zu erstellen?
Auszugsweise hier mal mit nur 4 verschiedene Masterreihen im Bezug auf Reihe1
 ABCDEFGHIJKLMNO
3ReihePos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
4Reihe 1223312313233331
5               
6Master1Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
7223323313233333
8okokokokokokokokokokokokok13
9               
10Master2Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
11233333313333336
12okokokokokokokokokokokokok13
13               
14Master3Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
15233332333333337
16okokokokokokokokokokokokok13
17               
18Master4Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
19223312333333334
20okokokokokokokokokokokokok13


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4
Ich weiß allerdings nicht ob ich Dir helfen kann.
Würde nur gern erstmal wissen, ob ich es jetzt richtig interpretiere?
Gruß Matthias

Anzeige
AW: ...bisschen anders/ergänzend erklärt
26.12.2014 15:17:20
Joerschi
Hi Matthias,
die Masterreihe wird nicht direkt für Reihe 1 (oder jede andere Reihe) erstellt.
Die MR soll letztlich so viele Reihen wir möglich aus der Tabelle abdecken (egal welche).
Folgender Ablauf wäre imo denkbar:
1. Excel erstellt x Masterreihen, welche die Summenbedingung erfüllt.
2. Nun prüft Excel MR für MR ab, welche dieser aus 1. erstellen MR die meisten Reihen aus der Basistabelle abdeckt.
LG, joerschi
PS: Bin heute noch unterwegs - kann heute nacht wieder antworten

AW: ...bisschen anders/ergänzend erklärt
26.12.2014 20:33:41
Matthias
Hallo
Ein weitere Versuch
Neu erstellte Reihen(per Zufall)
 ABCDEFGHIJKLMNOPQR
3ReihePos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S321
4Master-R1332232332131230652
5Master-R2323333132322131742
6Master-R3322313233113330733
7Master-R4232311232323330652
8Master-R5232323222332231580
9Master-R6333322322312130652
10Master-R7223233322322231580
11Master-R8311331333332231823
12Master-R9233332232213130652
13Master-R10222323113323330652
14Master-R11213133323313230733
15Master-R12213333332312231742
16Master-R131333312333333341012
17Master-R14233121223333230652
18Master-R15323323133321130733
19Master-R16221322331323330652
20Master-R17113332332331230733


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4

    Nur als Beispiel!
    Beim Klick auf CommandButton werden 17 Masterreihen gebildet deren Summe >=30 ergibt
    Die Zellen werden dabei per Zufall in den Positionen 1 bis 13 mit 1,2 oder 3 gefüllt
    Hat die Zelle O21 den Wert 17 sind alle Zeilen für dieses Beispiel fertig.
    Spalten(P,Q,R) sind nur Informationsspalten wie oft 3er,2er oder 1er vorhanden sind
    Sei nicht ungeduldig, kann mal schon einen Moment dauern bis alles gefüllt ist
    Was Du dann vergleichen willst hab ich immer noch nicht ganz gerafft.
    Vermutlich ist die am meisten abdeckende MasterZeile die in deren Zeile die 3 am meisten vorkommt

Zu vergleichende Reihen:
 ABCDEFGHIJKLMNOPQR
22ReihePos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13    
23Reihe 12233123132333S321
24Reihe 2331233313123331823
25Reihe 3333323233312334931
26Reihe 4332133131233230733
27Reihe 5323222313133230652
28Reihe 6132133333311330814
29Reihe 7232333232113230652
30Reihe 83333333331233361111
31Reihe 9122223333323231661
32Reihe 10122133323223330652
33Reihe 11333333121233131823
34Reihe 12132331233123330733
35Reihe 13333332332321233841
36Reihe 14332111233333230733
37Reihe 15331133212233330733
38Reihe 16233132213223330652
39Reihe 17323232223333233760


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4


https://www.herber.de/bbs/user/94597.xlsm
Gruß Matthias

Anzeige
AW: ...bisschen anders/ergänzend erklärt
26.12.2014 23:57:00
Joerschi
Hallo Matthias,
der Ansatz sieht schon mal sehr interessant aus.
Ich werde mich da mal reinarbeiten (sieht auf den ersten Blick nicht einfach aus) und wenig probieren bzw. würde Dir dann Feedback geben.
Auf jeden Fall vielen herzlichen Dank für die Mühe!
LG, Joerschi

(m)eine formeltechnische Annäherung ...
27.12.2014 19:14:37
neopa
Hallo Joerschi,
... gibt aber nur eine unvollständige weil ich keine eindeutige Lösung gefunden habe.
Wenn ich Dein Anliegen richtig verstanden habe, wird mE wohl mit großer Wahrscheinlichkeit Dein Vorgabewert in AC7 für eine "Masterreihe" größer sein müssen als das Maximum der Summenwerte der Datenreihen, wenn Du mit der "Masterreihe" mehr als nur minimal eine Datenreihe gemäß Deinen Vorgabe Bedingungen "vollständig abdecken" (="Treffer") willst.
Für Dein Datenreihenbeispiel ist es mir jedenfalls nicht gelungen für den Vorgabewert 30 mehr als eine zutreffende Datenreihe zu finden.
Mit meinen Formel für "MR2" in Q12 für Q12:AC12 (auf der Basis von mittels weiterer 6 Hilfsformeln ermittelten Daten) hab ich einen Vorschlag für eine mögliche Lösungsannäherung. Damit konnte ich z.B. für den Vorgabewert 34 in AC7 immerhin 4 "Treffer" ermitteln. (Matthias hat mit seiner hier dargestellten "34er" MR z.B. zwei Treffer, wie ich mit der aus Af12 kopierten Formel ermittele.
Andere Masterreihen, die möglicherweise noch eine Erhöhung der "Treffer" erbringen könnte, wird wohl nur mittels VBA ermittelbar sein.
Im nachfolgenden Beispiel (welches ich in zwei Tabellenhälften gesplittet habe) ist als MR1 die eine Masterreihe wiedergegeben, die immer mindestens einen "Treffer" ergibt, weil sie die identische Wiedergabe einer vorhandenen Datenreihe ist.
Alle nachfolgenden Formeln sind mit Ausnahme von AE12 entsprechend nach rechts zu kopieren, die Formel AF12 zusätzlich nach oben und unten und die für AE12 nur nach nach oben und unten:
 ABCDEFGHIJKLMNO
3 Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13S
4Reihe 1323211223312227
5Reihe 2223112333132228
6Reihe 3111322332233329
7Reihe 4221113233223227
8Reihe 5222123231213226
9Reihe 6112221223333328
10Reihe 7113323133332331
11Reihe 8223322213313128
12Reihe 9123222313231227
13Reihe 10132332213321329
14Reihe 11313321222133329
15Reihe 12112333313332230
16Reihe 13113322223322127
17Reihe 14113132333233331
18Reihe 15321312133233229
19Reihe 16132331213232329
20Reihe 17122331323331229
21               
22Hilfzeile 1.1962430151218214224332421 
23Hilfzeile 2.11314  23202726    29 
24Hilfzeile 3.12231  2829 20      
25               

Formeln der Tabelle
ZelleFormel
O4=SUMME(B4:N4)
B22=SUMMENPRODUKT(($O$4:$O$20<=$AC$7)*(B$4:B$20={3.3.3}))
B23=SUMMENPRODUKT(($O$4:$O$20<=$AC$7)*(B$4:B$20={2.3.3.3})*((Q22="")))
B24=SUMMENPRODUKT(($O$4:$O$20<=$AC$7)*(B$4:B$20={1.2.2.2})*(ANZAHL(Q$22:Q$23)=0))


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4
 PQRSTUVWXYZAAABACADAEAFAGAHAIAJAK
6                      
7 Vorgabe Bedingung - Gesamtsumme je Reihe in der Lösung/Masterreihe ist:34        
8 Masterreihe                   
9 Pos. 1Pos. 2Pos. 3Pos. 4Pos. 5Pos. 6Pos. 7Pos. 8Pos. 9Pos. 10Pos. 11Pos. 12Pos. 13SAnzahl x  : \ Reihen--Nr.   
10MR1:1133231333323311x :7     
11                      
12MR2:2233223233333344x :68913  
13                      
14 1333312333333342x :616    
15                      
16                      
17                      
18                      
19                      
20                      
21                      
22Hilfzeile 1.2  33    3333         
23Hilfzeile 2.2      3     3        
24Hilfzeile 3.222  22 2             
25                     3

Formeln der Tabelle
ZelleFormel
Q10{=INDEX($A:$N;3+VERGLEICH(MAX(($O$4:$O$99-$AC$7<=0)*$O$4:$O$99); $O$4:$O$99;); SPALTE(B1))}
Q12=WENN(ANZAHL(Q22:Q24)=0;1;MAX(Q22:Q24))
AD12=SUMME(Q12:AC12)
AE12=SUMME(N(HÄUFIGKEIT(($B$4:$N$20<=$Q12:$AC12)*ZEILE($A$1:$A$17); ZEILE($A$1:$A$17))=10+SPALTE(C$1)))&"x :"
AF12{=WENNFEHLER(INDEX(ZEILE($A$1:$A$17); KKLEINSTE(WENN(HÄUFIGKEIT(($B$4:$N$20<=$Q12:$AC12)*ZEILE($A$1:$A$17); ZEILE($A$1:$A$17))=13;ZEILE($A$1:$A$17)); SPALTE(A1))); "")}
AJ12{=WENNFEHLER(INDEX(ZEILE($A$1:$A$17); KKLEINSTE(WENN(HÄUFIGKEIT(($B$4:$N$20<=$Q12:$AC12)*ZEILE($A$1:$A$17); ZEILE($A$1:$A$17))=13;ZEILE($A$1:$A$17)); SPALTE(E1))); "")}
Q22=WENN(B22>KGRÖSSTE($B22:$N22;$AC7*2/3^2); 3;"")
Q23=WENN((B23>=KGRÖSSTE($B23:$N23;KÜRZEN(($AC7-SUMME($Q22:$AC22))/6;))); 3;"")
Q24=WENN(B24>=KGRÖSSTE($B$24:$N$24;($AC7-SUMME($Q22:$AC23))-13+ANZAHL($Q22:$AC23)); 2;"")
Enthält Matrixformel:
Umrandende
{ } nicht miteingeben,
sondern Formel mit STRG+SHIFT+RETURN abschließen!
Matrix verstehen


Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4
Gruß Werner
.. , - ...

Anzeige
AW: (m)eine formeltechnische Annäherung ...
28.12.2014 10:00:03
Joerschi
Hallo Werner,
hui - was für ein Formel"gewitter", der Ansatz scheint vom Überfliegen interessesant. Da muss ich mich jedoch erstmal rein- und durcharbeiten :-).
Danke Dir auf jeden Fall recht herzlich für die Mühe!
Viele Grüße
Joerschi

Links zu Excel-Dialogen

Beliebteste Forumthreads (12 Monate)

Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige
Anzeige
Anzeige