Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Geordnete Tupel erzeugen
Autor
Kein bestimmter Bereich Geordnete Tupel erzeugen
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3213
  Themenstart: 2022-09-27

Gegeben ist eine sortierte Liste reeller Zahlen. (Zur Vereinfachung können wir von paarweise unterschiedlichen Zahlen ausgehen) Gesucht ist ein Algorithmus, der effizient k-Tupel mit monoton steigender Summe generiert. Also bspw. für M = [1.0,2.1,2.8,4.0] und k = 2 soll der Algorithmus (1.0,2.1), (1.0,2.8), (2.1,2.8), (1.0,4.0), (2.1,4.0), (2.8,4.0) ausspucken. Ein Algorithmus zum (dublettenfreien) Erzeugen der Halbordnung der Tupel natürlicher Zahlen in Zusammenarbeit mit einer Prioritätswarteschlange sollte das Problem mMn. lösen. Dummerweise habe ich selbst mit diesem Teilproblem bereits Schwierigkeiten. Falls jemand ein passendes Stichwort für das Problem oder seine Lösung nennt, so ist das auch willkommen.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2352
Wohnort: Thüringen
  Beitrag No.1, eingetragen 2022-09-27

Also ich bin jetzt nicht der Profi, aber nehmen wir an : 10,21,28,40 (Komma liest sich schlecht) 1. Sortiere alle Zahlen der größe nach (Bubblesort oder so) / okay, sie ist ja sortiert 2. Kombiniere alle Zweiergruppen und schreibe sie in ein 2D-Feld Hier: 10;21 10;28; 10;40 21;28; 21;40 28;40 3. Sortiere wiederrum (Bubbelsort ?) die Summe beider Feldinhalte Da jetzt 21;28 < 10;40 wäre, müsste man eben , weil F(3,1)=10 und F(3,2)=40 sowie F(4,1)=21 und F(4,2)=28 ist, einfach den Inhalt tauschen SWAP F(3,1);F(4,1) ; SWAP F(3,2);F(4,2) Vorab ist eben Summe von F(x,1)+F(x,2) zu bilden um vergleichen zu können.... wenn es nicht gerade 1 Mio Kombinationen sind, würde ich es so machen. Allerdings für k>2 sehe ich da echt Probleme in der Umsetzung.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3213
  Beitrag No.2, vom Themenstarter, eingetragen 2022-09-27

Es geht daher darum, die Daten lazy zu generieren. Ich gebe mal ein Beispiel für einen Algorithmus, der das Problem grundsätzlich löst, aber noch offensichtliche Schwächen hat. 1. Starte mit (1*,2,3,...,k) // * bedeutet eine Markierung 2. Für i von *-Position bis k: Erhöhe das i-te Element und ggf. (rekursiv) seinen Nachbarn Lösche die Markierung und markiere das i-te Element Gib das entstandene Tupel als eines der Kinder zurück Für 2-Tupel der Liste (1,2,3,4) bedeutet dies: (1*,2) -> {(2*,3),(1,3*)} (1,3*) -> {(1,4*)} (2*,3) -> {(3*,4),(2,4*)} (1,4*),(3*,4),(2,4*) -> {} Mit Liste [10,21,28,40] als zugehörigen Werten sieht die Prioritätswarteschlange dann wie folgt aus: [(1*,2):31] => (1*,2) [(1,3*):38,(2*,3):49] => (1,3*) [(2*,3):49,(1,4*):50] => (2*,3) [(1,4*):50,(2,4*):61,(3*,4):68] => (1,4*) [(2,4*):61,(3*,4):68] => (2,4*) [(3*,4):68] => (3*,4) [] Jetzt wäre zu klären, wie viele Elemente die PQ maximal enthalten kann. Ein in i-ter Position markiertes Element besitzt maximal (k-i+1) Kinder. Der absolute Worstcase (exponentielles Wachstum mit Basis k) kann jedoch nicht eintreten, da "Kollisionskinder" immer hinter ihren Geschwistern in die PQ einrücken. Mathematiker vor: Wie ist also die Laufzeit?


   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1839
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
  Beitrag No.3, eingetragen 2022-09-28

Ich versuche bei Anforderungen solcher Art vorab zu prüfen, ob ich das Ganze als 'Verwandtschaft' von Karps 21 NP- vollständigen Problemen identifizieren kann. Mit zunehmendem zeitlichen und Alltagsabstand von einstiger eigener akademischen Fitness fällt mir das immer schwerer. Hier sehe ich bislang noch keine unmittelbare Verbindung. Eines scheint jedoch klar: Seien \(M=\{x_1,x_2,x_3,...\}\) eine geordnete Menge reeller Zahlen, und \(k\in\mathbb{N}_2\,[k\in\mathbb{N}\,\land\,k\geq2]\) die Größe von geordneten Tupeln mit Summanden aus \(M\) . Dann gilt für z.B. \(k=3\) stets: \(x_1+x_2+x_3\;\leq\;x_2+x_3+x_4\;\leq\;x_3+x_4+x_5\;\leq\;...\) , und die Tripel \((x_1,x_2,x_3)\) , \((x_2,x_3,x_4)\) , \((x_3,x_4,x_5)\) sollten auch alle in der 'PQ' enthalten sein. Mein Ansatz würde sich daran ausrichten, also im Rahmen einer übergeordneten Schleife nacheinander aufsteigend solche Paare benachbarter Tupel 'abgrasen', sie und ihre jeweiligen Summen als untere und obere Schranke an eine untergeordnete Routine übergeben, und mittels derer dann 'Lücken füllen'. Über Details wie mögliche Rekursion etc. brüte ich noch leidlich fruchtlos. 🙄


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3213
  Beitrag No.4, vom Themenstarter, eingetragen 2022-09-29

\quoteon(2022-09-28 21:56 - cramilu in Beitrag No. 3) Seien \(M=\{x_1,x_2,x_3,...\}\) eine geordnete Menge reeller Zahlen, und \(k\in\mathbb{N}_2\,[k\in\mathbb{N}\,\land\,k\geq2]\) die Größe von geordneten Tupeln mit Summanden aus \(M\) . Dann gilt für z.B. \(k=3\) stets: \(x_1+x_2+x_3\;\leq\;x_2+x_3+x_4\;\leq\;x_3+x_4+x_5\;\leq\;...\) , und die Tripel \((x_1,x_2,x_3)\) , \((x_2,x_3,x_4)\) , \((x_3,x_4,x_5)\) sollten auch alle in der 'PQ' enthalten sein. \quoteoff Es sollte genau das Gegenteil der Fall sein. Bei einem effizienten Algorithmus darf die PQ grundsätzlich nur das Minimum jeder totalgeordneten Teilmenge enthalten. Mathematisch für meinen Algorithmus: \[(S \in \operatorname{PQ}) \land (\operatorname{mark}(S)\leq \operatorname{mark}(T)) \land (\forall i: T_i \geq S_i) \Rightarrow T \notin \operatorname{PQ} \] Vermutung: Die maximale Länge der PQ entspricht der "Breite" des Hasse-Diagramms der zugehörigen Halbordnung. Diese wächst dummerweise exponentiell in $k$. (Zum Beweis betrachte man binäre Tupel bzw. Teilmengen)


   Profil
DerEinfaeltige hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]