| |
| Autor |
 Geordnete Tupel erzeugen |
|
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 3299
 |  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 
Dabei seit: 02.09.2017
Mitteilungen: 2456
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
Dabei seit: 11.02.2015
Mitteilungen: 3299
| 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
Dabei seit: 09.06.2019
Mitteilungen: 2652
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
Dabei seit: 11.02.2015
Mitteilungen: 3299
| 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. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 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]
|
Home / Seite ohne Frame
2023-11-29 20:23 ?
Wie unterstütze ich den Matheplaneten mit Geld?
