Rundreise frage (Algorithmus)

H

horstiii1

Gast
Mal eine Frage bei einer Rundreise die keiner Heuristik unterliegt wählt man doch immer die i+1. Stadt als nächstes aus, oder?
Also mein Beispiel bei 3 aus 5 Städten:
Code:
123 321
124 421
125 521
134 431
135 531
145 541
234 432
235 532
245 542
345 543

Aber wo ist jetzt wenn man 3 zuerst wählt zum Beispiel die Folge 312?
 
H

horstiii1

Gast
Lesen müsste man können :( Erste Reihe

(Man fängt mit der 3 an und geht nicht rückwärts)
 

MoxxiManagarm

Top Contributor
Ehrlich gesagt verstehe ich die Frage nicht wirklich.
Heißt das du willst die Kombination aus allen Städten, wobei Stadt #2 und Stadt #3 immer zusammen "links" oder zusammen "rechts" liegen und nicht etwa eins "links" und eins "rechts"? D.h. sowas wie 315 geht nicht?
 
H

horstiii1

Gast
D.h. sowas wie 315 geht nicht
Ich Dir mal farblich hervorgehoben.
Ehrlich gesagt verstehe ich die Frage nicht wirklich.
Eine Rundreise hört ja mit der vorletzten Stadt auf und geht dann wieder zur ersten Stadt.
Es gibt zwei Richtungen und die beginnende Stadt kann "im Kreis" beliebig gewählt werden.
D.h. 123 231 UND 312 SOWIE 321 213 UND 132 folgt aus 123.
Kapito?

Für die Länge der Rundreise und zB den Profit der Rundreise ist zwar die Richtung jedoch nicht deren Anfang/Ende relevant......

Aber wirklich mal ich bin kein Profi auf dem Gebiet.
 

mrBrown

Super-Moderator
Mitarbeiter
H

horstiii1

Gast
Und wie kommt man dann auf 2435 bei 4 aus 5?
Na so
Java:
    void rundreise(int[] a, int[] b, int c, int d) {
        if (c == b.length) {
            if (Arrays.equals(b, new int[]{2, 4, 3, 5})) {
                System.out.println(Arrays.toString(b));
            }
        }
       
        else {
            for (int i = c; i < a.length; i++) {
                b[c] = a[i];
                rundreise(a, b, c + 1, d);
            }
        }
    }

Java:
.rundreise(new int[]{1, 2, 3, 4, 5}, new int[4], 0, 0);

stimmst du überein?
 
X

Xyz1

Gast
So gehts:
Java:
    void rundreise(int[] a, int[] b, int c) {
        if (c == b.length) {
            System.out.println(Arrays.toString(b));
        }
     
        else {
            for (int i = c; i < a.length; i++) {
                b[c] = a[i];
                rundreise(a, b, i + 1);
            }
        }
    }

Code:
[1, 2, 3, 4]
[1, 2, 4, 5]
[1, 3, 5, 4]
[1, 4, 5, 5]
[2, 5, 3, 4]
[2, 5, 4, 5]
[3, 5, 5, 4]
[4, 5, 5, 5]

fange bei 2 an und lese [2, 5, 3, 4] rückwaärts

richtig oder nicht?

Richtig!

Ist doch nicht richtig.
 
H

horstiii1

Gast
Moin Mihe!

1. Was ist richtig?
Du brauchst alle Permutationen über die Liste aller Städte.

2. Und wie nennt man das Folgende? :
Java:
    void rundreisea(int[] a, int[] b, int c, int d, HashSet<Integer> set) {
        if (c == b.length) {
            System.out.println(Arrays.toString(b));
        } else {
            for (int i = d; i < a.length; i++) {
                //if (!set.contains(a[i])) {
                //set.add(a[i]);
                b[c] = a[i];
                rundreisea(a, b, c + 1, i + 1, set);
                //set.remove(a[i]);
                //}
            }
        }
    }

    void rundreiseb(int[] a, int[] b, int c, int d, HashSet<Integer> set) {
        if (c == b.length) {
            System.out.println(Arrays.toString(b));
        } else {
            for (int i = d; i < a.length; i++) {
                //if (!set.contains(a[i])) {
                //set.add(a[i]);
                b[c] = a[i];
                rundreiseb(a, b, c + 1, d + 1, set);
                //set.remove(a[i]);
                //}
            }
        }
    }

    void rundreisec(int[] a, int[] b, int c, int d, HashSet<Integer> set) {
        if (c == b.length) {
            System.out.println(Arrays.toString(b));
        } else {
            for (int i = 0; i < a.length; i++) {
                if (!set.contains(a[i])) {
                    set.add(a[i]);
                    b[c] = a[i];
                    rundreisec(a, b, c + 1, d + 0, set);
                    set.remove(a[i]);
                }
            }
        }
    }


        HideMe hideMe = new HideMe();
        int[] a = {1, 2, 3, 4};
        System.out.println("aaa");
        hideMe.rundreisea(a, new int[2], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreisea(a, new int[3], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreisea(a, new int[4], 0, 0, new HashSet<>());
        System.out.println("bbb");
        hideMe.rundreiseb(a, new int[2], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreiseb(a, new int[3], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreiseb(a, new int[4], 0, 0, new HashSet<>());
        System.out.println("ccc");
        hideMe.rundreisec(a, new int[2], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreisec(a, new int[3], 0, 0, new HashSet<>());
        System.out.println("");
        hideMe.rundreisec(a, new int[4], 0, 0, new HashSet<>());
        System.out.println("");

Code:
aaa (zu wenige, zum Beispiel 3124 ist nicht dabei)
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

[1, 2, 3, 4]
bbb (zu viele, doppelte --- und zu wenige, zum Beispiel 3124 ist nicht dabei)
[1, 2]
[1, 3]
[1, 4]
[2, 2]
[2, 3]
[2, 4]
[3, 2]
[3, 3]
[3, 4]
[4, 2]
[4, 3]
[4, 4]

[1, 2, 3]
[1, 2, 4]
[1, 3, 3]
[1, 3, 4]
[1, 4, 3]
[1, 4, 4]
[2, 2, 3]
[2, 2, 4]
[2, 3, 3]
[2, 3, 4]
[2, 4, 3]
[2, 4, 4]
[3, 2, 3]
[3, 2, 4]
[3, 3, 3]
[3, 3, 4]
[3, 4, 3]
[3, 4, 4]
[4, 2, 3]
[4, 2, 4]
[4, 3, 3]
[4, 3, 4]
[4, 4, 3]
[4, 4, 4]

[1, 2, 3, 4]
[1, 2, 4, 4]
[1, 3, 3, 4]
[1, 3, 4, 4]
[1, 4, 3, 4]
[1, 4, 4, 4]
[2, 2, 3, 4]
[2, 2, 4, 4]
[2, 3, 3, 4]
[2, 3, 4, 4]
[2, 4, 3, 4]
[2, 4, 4, 4]
[3, 2, 3, 4]
[3, 2, 4, 4]
[3, 3, 3, 4]
[3, 3, 4, 4]
[3, 4, 3, 4]
[3, 4, 4, 4]
[4, 2, 3, 4]
[4, 2, 4, 4]
[4, 3, 3, 4]
[4, 3, 4, 4]
[4, 4, 3, 4]
[4, 4, 4, 4]
ccc (zu viele, 1234 ist dasselbe wie 2341 ist dasselbe wie 3412 ist dasselbe wie 4123 ist dasselbe wie 4321 und so weiter ... )
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 4]
[4, 1]
[4, 2]
[4, 3]

[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Bitte um einen kleinen Tipp.
 

mihe7

Top Contributor
Bitte um einen kleinen Tipp.
Aktuell nur: meine erste Aussage war nicht korrekt, weil nicht alle Permutationen benötigt werden, wie Du bereits richtig geschrieben hast. D. h. für eine Folge mit n Zeichen gibt es durch Rotation n Belegungen, die zu einem identischen Ergebnis führen. Die Zahl der Möglichkeiten bei n Städten (n aus n) dürfte sich somit von n! auf n!/n = (n-1)! reduzieren.
 
X

Xyz1

Gast
Es sieht aber noch nach n hoch n oder n Fakultät aus , also die 1 Mio Frage ist damit nicht gelöst. :oops: Nüschts sehr Neues.... Nur wie der algo. falls eine Bezeichnung heißt weiß ich nich :(
 

mihe7

Top Contributor
a) ich weiß nicht, ob es einen Algorithmus gibt, der nur "rotationsfremde" (ich nenne sie einfach mal so) Permutationen konstruiert
b) wie ein solcher Algorithmus heißen würde, weiß ich leider auch nicht :)
c) wesentlich ist, dass es (n-1)! "rotationsfremde" Permutationen gibt. Falls a) existiert, dann geht es nur um die Frage, ob (n-1)! oder n! Kombinationen "betrachtet" werden. Das spielt für die Komplexität des Problems aber keine Rolle.
 
X

Xyz1

Gast
zu a) Es wird ihn geben, auch wenn ich so schnell auf stackoverflow com nichts dazu gefunden habe
zu b) und c) Das ist richtig, Danke Dir für Deine Mühen....
zur Komplexität Das ist richtig die Komplexität ist nicht auf einmal "verringert", zudem kein Beweis das eine "Verringerung"/reduktion nicht möglich sei

In diesem Thema ist doch eigentlich alles schon beantwortet falls nun iewo das Wort "rotationsfremd"(/~"arotational") entsteht weiß ich was damit gemeint sei :D
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
KonradN Mal eine Frage zu Binary Serialization Allgemeine Java-Themen 15
8u3631984 Frage zu Java Streams min / max Allgemeine Java-Themen 17
8u3631984 Frage Performance bei Linked List und Array List Allgemeine Java-Themen 5
H Frage regex greater than less than Allgemeine Java-Themen 7
berserkerdq2 Frage zu IntelliJ und JavaFX Allgemeine Java-Themen 1
W Timer Konzept-Frage Allgemeine Java-Themen 16
T Eine Frage des Designs Allgemeine Java-Themen 2
C Frage zu eigenem TableCellRenderer Allgemeine Java-Themen 11
C Programmvorstellung & Frage zum Thema Geschäftsform Allgemeine Java-Themen 51
J Frage zu System.getproperties. Allgemeine Java-Themen 60
molat100 wie kann man die Frage beantworten Allgemeine Java-Themen 1
pkm Frage zur Präzision von Calendar.WEEK_OF_YEAR Allgemeine Java-Themen 12
J Eine Frage zu den Threads und Task Allgemeine Java-Themen 1
pkm Frage nach eventuellem syntaktischen Zucker bei der Konkatenation von ArrayLists Allgemeine Java-Themen 4
M Frage-Antwortspiel wie Wer wird Millionär Allgemeine Java-Themen 1
F Frage zu System.in Allgemeine Java-Themen 3
marcooooo Frage zum Beispiel im Anhang Allgemeine Java-Themen 16
T Meine Frage lautet wie ich 2 CSV Dateien miteinander in Java verbinde und Spalten die zueinander gehören durch den gleichen Key zusammen ausgebe? Allgemeine Java-Themen 5
S Noch eine Design-Frage zu Setter Allgemeine Java-Themen 6
B For-Loop Frage Allgemeine Java-Themen 21
L Java frage Allgemeine Java-Themen 3
bueseb84 Frage zu Mock und UpperBound Allgemeine Java-Themen 2
M Frage zum Konstruktor Allgemeine Java-Themen 2
W Best Practice Frage zur Umsetzung MVC Allgemeine Java-Themen 9
P String-Verschlüsselung - Frage zur Sicherheit Allgemeine Java-Themen 21
B Frage zu Unit-Tests Allgemeine Java-Themen 6
T Allgemeine Frage: GUI für 3D-Visualisierung Allgemeine Java-Themen 5
R Allgemeine Frage zu RMI bei MVC Allgemeine Java-Themen 2
O Frage zum Runtimeverhalten von Java ... Allgemeine Java-Themen 2
B Generelle Frage bei einer Webanwendung / Reduzierung von DB Abfragen Allgemeine Java-Themen 1
D Frage zu Vererbung Allgemeine Java-Themen 5
J Frage zu regulärem Ausdruck Allgemeine Java-Themen 2
M Allgemeine Frage: Wie lernt man Java / Programmieren von Grund auf? Allgemeine Java-Themen 7
rentasad Design-Frage - Interfaces, Klassen, statische Methoden Allgemeine Java-Themen 3
S Frage zur JLS Allgemeine Java-Themen 0
J Verständnis Frage zur Instanz, Objekte, Instanzierung, Referenz Allgemeine Java-Themen 14
A Methoden Allgemeine Java Frage Allgemeine Java-Themen 3
E String Frage Allgemeine Java-Themen 9
I bin neu bei GitHub, Frage zur Sicherheit Allgemeine Java-Themen 14
C J2V8 NodeJs Java Bride Problem und Frage!?!? Allgemeine Java-Themen 1
C KeyListener Frage Allgemeine Java-Themen 3
T Frage zu UML in Java programmieren Allgemeine Java-Themen 1
R Konstanten initialisieren - FRAGE Allgemeine Java-Themen 3
MTJ004 FTP Frage zu FTP Speicherung Java-Android-FTP Allgemeine Java-Themen 5
J Frage zum Entwurf / json-Datenmodell Allgemeine Java-Themen 8
A Frage zu meinem Code Allgemeine Java-Themen 2
RalleYTN Classpath Nur ne kleine Frage zur MANIFEST.MF Allgemeine Java-Themen 4
T Frage zu Access Modifiers Allgemeine Java-Themen 6
W Input/Output Frage zu pdfbox und FileUtils Allgemeine Java-Themen 2
O Frage zur Implementierungsweise Allgemeine Java-Themen 4
B Frage zu Bitshift Allgemeine Java-Themen 3
J Java Zufallsgenerator (6 aus 49) Frage Allgemeine Java-Themen 7
L Frage zu RIA und GWT Allgemeine Java-Themen 0
P Concurrency Frage Allgemeine Java-Themen 8
M Frage zu Enumerations Allgemeine Java-Themen 2
F Unlimited Strength Policy. Frage Verbreitung der Anwendung Allgemeine Java-Themen 1
F Frage zur Library JTS Allgemeine Java-Themen 5
S Java Design Frage Allgemeine Java-Themen 10
E Reflection? Frage Allgemeine Java-Themen 4
C FileInputStream frage Allgemeine Java-Themen 6
G Polymorphie Programmdesign Frage Allgemeine Java-Themen 20
Uzi21 Frage zu NetBeans ( Console) Allgemeine Java-Themen 11
D Classpath Frage zum Java Resource Loading Allgemeine Java-Themen 2
G Frage zu JPA Allgemeine Java-Themen 1
S Methoden Frage Allgemeine Java-Themen 2
P MVC - Frage zu Model Allgemeine Java-Themen 4
K Frage zu Locks Allgemeine Java-Themen 1
S Frage zu abstract Allgemeine Java-Themen 5
M ArrayList<String> Frage Allgemeine Java-Themen 7
M OOP Design Frage Allgemeine Java-Themen 2
N Frage zur while-Schleife Allgemeine Java-Themen 18
T Best Practice Auslesen von Zeichenketten (Frage, Antworten, usw) Allgemeine Java-Themen 4
C Eine Frage zur Bearbeitungszeit Allgemeine Java-Themen 8
H Frage wegen Heap-Speicher Allgemeine Java-Themen 2
T Garbage Collection Frage Allgemeine Java-Themen 15
P Kurze Frage: aus einer File die Zeilenanzahl auslesen Allgemeine Java-Themen 9
D Frage zu Java und Umlauten / charsets Allgemeine Java-Themen 2
B Frage zu Java und OpenGL? Allgemeine Java-Themen 3
Q Kapselung Allgemeine Design- Frage Allgemeine Java-Themen 8
A eine test thread.join() frage Allgemeine Java-Themen 2
DStrohma LayoutManager Frage zum GridBagLayout Allgemeine Java-Themen 4
F Frage zu Regex möglich Allgemeine Java-Themen 4
H XML-File mit Java erzeugt Frage Allgemeine Java-Themen 10
D Frage und Antwort Programm, Problem bei Methodenaufruf Allgemeine Java-Themen 3
J NetBeans Frage bezüglich der Scanner-Klasse Allgemeine Java-Themen 6
H Java Vector Frage Allgemeine Java-Themen 9
W Frage... Allgemeine Java-Themen 29
R Frage zur topologischen Sortierung Allgemeine Java-Themen 2
H Frage zu weka.core.Instance Allgemeine Java-Themen 3
Y Kleine Frage zu String.split Allgemeine Java-Themen 3
T Frage zu Klassendesing Allgemeine Java-Themen 3
W Frage zu Refactoring statischer Methoden Allgemeine Java-Themen 4
C Eclipse Wichtige frage Allgemeine Java-Themen 5
H Frage zu java.weka.core.Instances Allgemeine Java-Themen 3
S Frage zu Format Modifiers in Log4j Allgemeine Java-Themen 11
H Frage zu clone() Allgemeine Java-Themen 5
4 Simple(?) Frage zu Threads Allgemeine Java-Themen 14
H2SO3- SCJP Chapter 3 Frage 10. Falsche Antwort? Allgemeine Java-Themen 15
H Frage sinnvolle Datenspeicherung und -verarbeitung Allgemeine Java-Themen 3
EnHancEd[] kurze enum-Frage Allgemeine Java-Themen 4

Ähnliche Java Themen

Neue Themen


Oben