Einträge aus Tupeln nach Regeln in Liste speichern

A

AshCatchem

Mitglied
Guten Abend zusammen, ich komme bei meiner Programmieraufgabe nicht weiter und benötige eure Hilfe.

Ich muss Wegpunkte einer Route hinzufügen. Diese Wegpunkte haben einen Nachbarn und sind gemeinsam mit deren Score in einem Objekt gespeichert. Dieses Tupel hat widerum einen Score.
Als aufgeschriebene Liste sähe das so aus :

Wegpunkte, Bewertung
(3,5), 100
(4,6), 91
(1,7) 87
(3,6) 80
(5,6) 77 usw.

Ich muss nun die Wegpunkte absteigend nach deren Score in die Route speichern. In diesem Fall also 3,5,6,4,...

Auf dem Papier kann ich das, aber ich bekomme es nicht in den PC. Das sortieren der Tupel nach deren Score ist kein Problem, allerdings komme ich bei den ganzen erforderlichen Schleifen und Bedingungen durcheinander, wenn es darum geht, die Route zu bilden. Kann mit jemand auf die Sprünge helfen? Ich würde gerne selbst auf die Lösung kommen.

Viele Grüße
 
H

httpdigest

Top Contributor
Meine Vermutung ist, dass die Pfadsegmente in beide Richtungen traversierbar sind, und sie nur in irgendeiner kanonischen Form aufgeschrieben werden mussten (also niedrigste Zahl zuerst). Ich nehme an, dass ein (a, b) dasselbe ist wie ein (b, a).
Das heißt: (3, 5) -> (5, 6) -> (4, 6). Der letzte wäre dann 6 -> 4.
 
A

AshCatchem

Mitglied
Entschuldigt bitte die unklare Formulierung. Sowie es httpdigest beschreibt, ist es richtig, allerdings mit einem entscheidenden Hinweis: Standorte befinden sich nur einmal in einer Route . Die Werte in den Klammern sind Indizes für Standorte. (a, b) entspricht (b, a) und es wird nach absteigendem Score sortiert. Weil man einen Ort nicht doppelt besucht, fliegt der natürlich raus. Ich habe deshalb auch diese "doppelten" Einträge in meinem sortierten Array erlaubt (anders als hier aufgeschrieben), damit das einfacher zu handhaben ist. Mir fällt bloß keine allgemeingültige Vorschrift ein, wie ich das umsetzen soll. Mein Ansatz wäre mit vielen if Verzweigungen und das gefällt mir gar nicht. Wie gehe ich sowas am besten an?
 
Zuletzt bearbeitet:
H

httpdigest

Top Contributor
Wenn die Paare reflexiv sind, dann ist mir eigentlich nur unklar, woher du weißt, mit welchem Ort/Knoten genau angefangen werden soll. Das Pfadsegment (3, 5) kann ja heißen, dass mit 3 oder mit 5 angefangen werden kann. Und das wiederum bedingt, welche nächsten Pfadsegmente verwendet werden können, die unterschiedliche Scores haben können. Woher weißt du also am Anfang bei (3, 5), dass auch mit 3 -> 5 und nicht eben mit 5 -> 3 begonnen werden soll?

Der letzte Weg ist nicht von 6 zu 4, da 4 bereits in der Route vorkommt.
Ach nein? Wo kommt denn 4 schon vor, wenn nicht ganz am Schluss von 6 -> 4? Und wie kommst du dann auf 3,5,6,4?
 
A

AshCatchem

Mitglied
Hab's in meinem Post korrigiert, alles gut. Das ist ein berechtigter Einwand. Als erster Ansatz wird beim ersten Weg vorgeschrieben, dass dieser in aufsteigender Reihenfolge der Indizes abzulaufen hat.
 
H

httpdigest

Top Contributor
Hier ist schonmal eine mögliche inperformante Lösung:
Java:
import static java.lang.Integer.compare;
import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;
import java.util.*;
public class Path {
  public static void main(String[] args) {
    // Repräsentation eines Pfadsegmentes
    class Segment implements Comparable<Segment> {
      int a, b, score;
      Segment(int a, int b, int score) {
        this.a = a;
        this.b = b;
        this.score = score;
      }
      // Zum Sortieren nach Score und kanonischer
      // Reihenfolge (a, b) mit a < b
      public int compareTo(Segment o) {
        int byScoreDesc = compare(o.score, score);
        int byA = compare(a, o.a);
        int byB = compare(b, o.b);
        return byScoreDesc != 0
            ? byScoreDesc
            : byA != 0 ? byA : byB;
      }
      public String toString() {
        return "(" + a + ", " + b + "), " + score;
      }
      // Zum Entfernen von Duplikaten
      public int hashCode() {
        return a ^ b;
      }
      // Zum Entfernen von Duplikaten
      public boolean equals(Object obj) {
        Segment other = (Segment) obj;
        return a == other.a && b == other.b
            || a == other.b && b == other.a;
      }
    }
    // Eingabeliste (wie vom ersten Post, nur
    // shuffled und mit (a, b) == (b, a) Duplikaten)
    List<Segment> segments = asList(
      new Segment(4, 6, 91),
      new Segment(5, 6, 77),
      new Segment(6, 3, 80),
      new Segment(1, 7, 87),
      new Segment(6, 5, 77),
      new Segment(5, 3, 100),
      new Segment(7, 1, 87),
      new Segment(3, 6, 80),
      new Segment(6, 4, 91),
      new Segment(3, 5, 100)
    ).stream()
     .sorted() // <- sortieren nach Score und nach (a, b) mit a < b
     .distinct() // <- Entfernen von Duplikaten (a, b) == (b, a)
     .collect(toList());
    // Erstes Pfadsegment ist immer das mit
    // dem höchsten Score
    Segment first = segments.remove(0);
    // Erzeuge mutable result Liste mit initial
    // a -> b aus dem ersten Pfadsegment
    List<Integer> result = new ArrayList<>(
        asList(first.a, first.b)
    );
    // next enthält immer den als nächstes zu suchenden Startpunkt
    int next = first.b;
    // Ermittle alle nachfolgenden Pfadsegmente
    do {
      final int n = next;
      Integer i = segments
          .stream()
          // Ermittle erstes/höchstes Pfadsegment mit passendem Startpunkt
          .filter(s -> s.a == n && !result.contains(s.b)
                    || s.b == n && !result.contains(s.a))
          .findFirst()
          .map(s -> s.a == n ? s.b : s.a) // <- Endpunkt
          .orElse(null); // <- nichts mehr gefunden. Ende!
      if (i == null)
        break;
      result.add(next = i);
    } while (true);
    // Ergebnis ausgeben
    System.out.println(result);
  }
}
 
A

AshCatchem

Mitglied
Danke für die Antwort, die Lösung sieht echt Klasse aus. Ich werde versuchen, die auf meine Art und Weise in meinen Code zu integrieren, aber ich habe noch einige Fragen. 1. Hast du Tipps, wie man seine Gedanken besser in Code bekommt? Dadurch, dass ich das auf dem Papier lösen kann, weiß ich ja, worum es geht. Wie formuliert man die einzelnen Schritte am besten? Kann man das einfach, muss man das lernen oder gibt es dafür Methoden? Ich bin echt beeindruckt, dass du das so schnell aus dem Ärmel geschüttelt hast. Ich hab da gestern den ganzen Tag dran gesessen und es nicht hinbekommen. Und ich will auch nicht als Ausrede nehmen, dass ich kein Informatiker bin.
2. Gehören deine genutzten Methoden in den Werkzeugkasten eines Anfängers oder ist das eher Wissen für Fortgeschrittene? Ich sehe bei dir keine einzige Schleife mit Laufvariable. Ich hab bei einem Ansatz 3 for Schleifen genutzt. Vermutlich denke ich noch zu kompliziert, aber das spornt mich irgendwie an, mich dahingened weiterzubilden. Ich war selten so oft davor, irgendwas hinzuschmeißen wie bei dem Projekt, obwohl das an sich ja echt leicht zu sein scheint. Wie lernt man am besten, so pragmatisch zu programmieren?

Viele Grüße
 
H

httpdigest

Top Contributor
Hast du Tipps, wie man seine Gedanken besser in Code bekommt? Dadurch, dass ich das auf dem Papier lösen kann, weiß ich ja, worum es geht. Wie formuliert man die einzelnen Schritte am besten? Kann man das einfach, muss man das lernen oder gibt es dafür Methoden?
Du brauchst dafür ein Verständnis für grundlegende algorithmische Primitive. Im Studium beginnt man dafür meist mit Nassi-Shneidermann-Diagrammen.
Deine Aussage, du hast es auf dem Papier bereits gelöst, ist ja beliebig interpretierbar. Es kann heißen, dass du einfach nur deine Eingabeliste hingeschrieben hast und dann grafisch Pfeile vom 1. zum 2. zu verwendenden Wegpunkt, dann zum 3. und dann zum 4. gezogen hast und vielleicht noch eine Notiz "Erst das, dann das und dann den hier" geschrieben hast. Das ist natürlich noch kein Algorithmus, da es keine klar strukturierten Anweisungen enthält.
Bezüglich Methoden/Techniken, kenne ich eigentlich nur Abstraktion und Dekomposition. Google die mal.

Und ich will auch nicht als Ausrede nehmen, dass ich kein Informatiker bin.
Das wäre ehrlich gesagt aber eine sehr gute Ausrede. Ein M.Sc. Informatikstudium zum Beispiel dauert ja nicht ohne Grund mindestens 5 Jahre.

Gehören deine genutzten Methoden in den Werkzeugkasten eines Anfängers oder ist das eher Wissen für Fortgeschrittene? Ich sehe bei dir keine einzige Schleife mit Laufvariable.
Da wären wir bei dem Thema Abstraktion. In der genutzten Stream API von Java verstecken sich die Schleifen. Da eine Schleife zu sehen das Ganze meiner Meinung nach aber nur komplizierter zu verstehen macht, da man die Laufvariablen (sprich: den Zustand) hier und dort immer im Kopf haben muss, habe ich einfach eine Möglichkeit gewählt, von der tatsächlichen Iteration zu abstrahieren, damit das tatsächliche Problem erkennbar wird (nämlich das Finden des ersten Pfadsegmentes, das mit seinen Endpunkten passt). Aber ich würde sagen, solche funktionale Programmierung ist definitiv Fortgeschrittenen-Niveau.

Ich war selten so oft davor, irgendwas hinzuschmeißen wie bei dem Projekt, obwohl das an sich ja echt leicht zu sein scheint. Wie lernt man am besten, so pragmatisch zu programmieren?
Versuche dich vielleicht an einfacheren Problemen (deins war schon ein bisschen von der Sorte "für Fortgeschrittene"). Und dann einfach viiiieele viiieeele Jahre üben üben und nochmals üben.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
C Erste Schritte JComboBox Einträge auf Duplikat prüfen Java Basics - Anfänger-Themen 4
S CSV auf doppelte Einträge überprüfen Java Basics - Anfänger-Themen 8
K Datentypen Einträge zweier Matrizen vergleichen Java Basics - Anfänger-Themen 4
I Einträge in den Konstruktor Java Basics - Anfänger-Themen 3
S Problem: Array alle Einträge gleich Java Basics - Anfänger-Themen 10
M Erste Schritte JList einträge Java Basics - Anfänger-Themen 1
P Erste Schritte Einträge aus verschachtelter Map chronoligisch ausgeben Java Basics - Anfänger-Themen 5
C JList Einträge nach Datum sortieren Java Basics - Anfänger-Themen 3
T Einträge in jComboBox aus Liste übernehmen Java Basics - Anfänger-Themen 1
S Wie bestehende Excel-Einträge mit neuen Vergleichen (mit Apache POI)? Java Basics - Anfänger-Themen 0
E Array doppelte Einträge Java Basics - Anfänger-Themen 2
S Variablen Array in ArrayList auf doppelte Einträge überprüfen Java Basics - Anfänger-Themen 4
T Alte Einträge im Array werden von neuen überschrieben Java Basics - Anfänger-Themen 5
P Doppelte Einträge in eine List Java Basics - Anfänger-Themen 5
D Javaliste auf gleiche Einträge überprüfen Java Basics - Anfänger-Themen 2
C Doppelte Einträge aus String [] Array entfernen. Java Basics - Anfänger-Themen 5
C Datentypen Array-Einträge überhalb der Array-Länge - welcher Wert? Java Basics - Anfänger-Themen 5
L Erste Schritte Einträge in ArrayList prüfen Java Basics - Anfänger-Themen 4
M Ziffer einträge vergrößern Java Basics - Anfänger-Themen 16
H Einträge aus Array löschen Java Basics - Anfänger-Themen 8
J Markierte Einträge (Dateien) in JList sollen in einen anderen Ordner verschoben werden. Java Basics - Anfänger-Themen 12
K ArrayList.add() überschreibt vorhandene Einträge. Java Basics - Anfänger-Themen 12
M Gewisse Einträge aus einer ArrayList löschen Java Basics - Anfänger-Themen 3
M doppelte Einträge Emailempfänger... Java Basics - Anfänger-Themen 35
K ArrayList Zugreifen auf Einträge Java Basics - Anfänger-Themen 8
G txt-File als DB>doppelte Einträge verhindern/Suche/... Java Basics - Anfänger-Themen 10
B 2D-Array, gleiche Einträge prüfen Java Basics - Anfänger-Themen 5
F Hiberate-Log-Einträge Java Basics - Anfänger-Themen 2
J Datentypen List - gleiche Einträge bei neuen Objekten Java Basics - Anfänger-Themen 31
Beckenbauer OOP Durch Komma getrennte Einträge in einem String in ein Array oder eine Tabelle schreiben Java Basics - Anfänger-Themen 4
kitz Mehrere Einträge auswerfen? Java Basics - Anfänger-Themen 20
P Doppelte Einträge in mehreren Textfiles finden und ausgeben Java Basics - Anfänger-Themen 8
E Darstellung der Choice Einträge Java Basics - Anfänger-Themen 4
K Datentypen Liste: Einzelne Einträge ändern Java Basics - Anfänger-Themen 2
L Tray-Einträge und dazu passende ActionListener dynamisch erzeugen? Java Basics - Anfänger-Themen 2
J doppelte Einträge in einem Array Java Basics - Anfänger-Themen 7
M Einträge in Dateien zählen - Performance-Problem Java Basics - Anfänger-Themen 10
M Einträge in JComboBox farblich hinterlegen? Java Basics - Anfänger-Themen 2
-horn- Doppelte Einträge entfernen, aus Array, List oder sonstwas Java Basics - Anfänger-Themen 9
G _NUR_ doppelte Einträge in einem Array behalten Java Basics - Anfänger-Themen 3
B Einträge im JList einfügen Java Basics - Anfänger-Themen 9
G doppelte Einträge im String Array löschen Java Basics - Anfänger-Themen 21
V Vector/Arraylist hat nur gleiche Einträge Java Basics - Anfänger-Themen 3
0 ArrayList - doppelte Einträge entfernen? Java Basics - Anfänger-Themen 9
S Methode, um doppelte Einträge in Array zu finden Java Basics - Anfänger-Themen 5
G Wie doppelte Einträge in ComboBox vermeiden ? Java Basics - Anfänger-Themen 9
M Doppelte Einträge in einer datei löschen(nach timestamp)! Java Basics - Anfänger-Themen 4
D Doppelte Einträge einer Liste löschen Java Basics - Anfänger-Themen 6
ARadauer Alle Einträge im Startverzeichnis Java Basics - Anfänger-Themen 5
B 2 ELists vergleichen und doppelte Einträge löschen Java Basics - Anfänger-Themen 11
M einträge farblich hervorheben ? Java Basics - Anfänger-Themen 8
M Vector soll keine doppelten Einträge enthalten! Java Basics - Anfänger-Themen 5
M Einträge einer .txt-Datei in einem TextField ausgeben lassen Java Basics - Anfänger-Themen 8
J Wie kann man im Systempopup einträge machen z.B im Explorer? Java Basics - Anfänger-Themen 6
K mehrere DB Einträge in einem JTable darstellen ?HILFE! Java Basics - Anfänger-Themen 2
G Array-Listen vergleichen und Einträge löschen ? Java Basics - Anfänger-Themen 4
S JList Einträge löschen Java Basics - Anfänger-Themen 3
B Nach eingefügtem Code erkennt Compiler keine Instanzvar und meldet SyntaxError Java Basics - Anfänger-Themen 2
newcomerJava Nach doppelter Zahl eine Ausgabe Java Basics - Anfänger-Themen 10
M Anzahl Schleifendurchgänge nach x Sekunden anzeigen Java Basics - Anfänger-Themen 2
C Lotto 3, 4, 5, 6 Richtige nach x Ziehungen ermittelt.. Java Basics - Anfänger-Themen 7
G Primzahlen von Rekursiv nach Iterativ Java Basics - Anfänger-Themen 6
F JMenuItem Kann nicht nach einem String benannt werden... Java Basics - Anfänger-Themen 11
R JDK installieren Durcheinander nach installation von SE 14.02 Java Basics - Anfänger-Themen 6
P Sortieren von Listen nach Attributen Java Basics - Anfänger-Themen 3
B DateTimeFormatter nach LocalDateTime, wenn dd.MM.yyyy oder dd.MM.yyyy mm:hh Java Basics - Anfänger-Themen 5
1 main-Methode erweitern, Nachfrage nach wiedeholung Java Basics - Anfänger-Themen 2
G unklares Verhalten nach Instanzierung neuer Klasse Java Basics - Anfänger-Themen 3
S Wohin kommt das „abstract“? Vor oder nach „public“/ „private“ /... Java Basics - Anfänger-Themen 3
S Datenbank Befehl nach Login Java Basics - Anfänger-Themen 5
N Operatoren Schreibtischtest der Reihen-Suche nach Aufschluss in die Basics Java Basics - Anfänger-Themen 1
B Umstieg von C# nach Java Java Basics - Anfänger-Themen 18
Ellachen55 Wie nach häufigste Werte im Array suchen? Java Basics - Anfänger-Themen 2
M Untersuchen ob ein Graph nach entfernen einer Kante immer noch zusammenhängend ist Java Basics - Anfänger-Themen 70
N Wörter und Zahlen nach speziellen Wörtern ausgeben Java Basics - Anfänger-Themen 11
M Werte ändern sich nicht mehr nach Reset Java Basics - Anfänger-Themen 14
B Nach dem kompilieren werden Bilder nicht mehr gefunden Java Basics - Anfänger-Themen 10
X Nach einem Bruch testen ob es eine ganze Zahl ist Java Basics - Anfänger-Themen 6
B String nach erstem Leerzeichen trennen Java Basics - Anfänger-Themen 7
N Speichern von Werten in Variablen nach Schließen des Programms Java Basics - Anfänger-Themen 3
G String wird nach Einlesen aus Datei nicht erkannt Java Basics - Anfänger-Themen 3
UnknownInnocent Best Practice Algorithmus nach jedem Schritt zum Visualisieren pausieren Java Basics - Anfänger-Themen 3
O zwei Arrays nach Werten durchsuchen und zusammenfügen Java Basics - Anfänger-Themen 3
M Double Wert nach n abschneiden ohne zu runden Java Basics - Anfänger-Themen 1
C Erste Schritte Bilder nach Export anzeigen Java Basics - Anfänger-Themen 0
F Input/Output Files von A nach B kopieren Java Basics - Anfänger-Themen 11
B InputStream (PDF) nach Image (PNG / JPG) konvertieren? Java Basics - Anfänger-Themen 2
O ADT Graph nach größe Abfragen Java Basics - Anfänger-Themen 42
O compareTo nach mehreren Kriterien Java Basics - Anfänger-Themen 13
R Benutzereingaben als Array abspeichern nach Programmstart Java Basics - Anfänger-Themen 5
S Pane nach speziellen Child Objekten durchsuchen Java Basics - Anfänger-Themen 3
V Neue Ausgabe von toString nach Methodenaufruf Java Basics - Anfänger-Themen 9
L Arrayliste von hinten nach vorne ausgeben Java Basics - Anfänger-Themen 10
F Array nach Objektattribut durchsuchen Java Basics - Anfänger-Themen 6
M Rationale Zahl erkennen - Kurze Frage zum Restwert nach Division Java Basics - Anfänger-Themen 3
O String von vorne nach hinten an einem Zeichen Java Basics - Anfänger-Themen 10
Hanschyo Quicksort sortiert von groß nach klein Java Basics - Anfänger-Themen 3
S suche nach varible POSITION ... fuer das pixel-maennchen Java Basics - Anfänger-Themen 4
B String nach HTML formatieren Java Basics - Anfänger-Themen 9
Zrebna Compiler-Fehler Java-Compiler wird nach 'javac' keyword-Eingabe nicht gestartet (Erste Übung) Java Basics - Anfänger-Themen 18

Ähnliche Java Themen

Anzeige

Neue Themen


Oben