Geordnete Arrays ausgeben

[rosima26]

Moin, ich soll alle Permutationen eines Arrays ausgeben. Dabei soll dann geprüft werden ob das Array geordnet ist sprich 1,2,3,4,5 oder 5,4,3,2,1 usw. Beibehalten werden sollen nur diese geordneten Arrays
Die Permutationen hab ich, mit dem ordnen tu ich mir schwer, hier der Code, bin dankbar für Tipps, LG

public class Permutationen {

    void printArr(int a[]) {

        for (int k = 0; k < a.length; k++)
            System.out.print(a[k]);
        System.out.println();
    }

    void Permutation(int a[], int size) {

        if (size == 1)
            printArr(a);

        for (int i = 0; i < size; i++) {

            Permutation(a, size - 1);

            if (size % 2 == 1) {
                int temp = a[0];
                a[0] = a[size - 1];
                a[size - 1] = temp;
            } else {
                int temp = a[i];
                a[i] = a[size - 1];
                a[size - 1] = temp;
            }
        }
    }

}

 

[KonradN]

Kannst Du denn in Worten beschreiben, was denn genau getan werden soll?

Derzeit hast Du sowas wie:

Für jede Permutation
- gib die Permutation aus

Was wäre denn das, was Du willst? Und kannst Du es im Detail beschreiben, was die einzelnen Schritte genau bedeuten?

 

[rosima26]

".." die systematisch alle Permutationen der Elemente eines Arrays a generiert und für jede von Ihnen prüft, ob sie sortiert ist. Ist das der Fall, wird diese Permutation beibehalten. Bei einer Permutation kann die Reihenfolge der Elemente des Arrays beliebig geändert werden. "..."

 

[KonradN]

Die Frage zielte nicht auf die genaue Aufgabenstellung ab sondern darauf, dass Du beschreibst, was ich machen soll. Ich kann jetzt Permutationen bilden und diese ausgeben. Aber was soll ich bitte machen? Ich bin jetzt hier sozusagen ein ganz einfacher, dummer Mensch - wie einem Computer musst Du mir genau sagen, was ich tun soll.

 

[rosima26]

Also mein Code kann ja die Permutationen ausgeben. Das heisst wenn ich 1,2,3,4 übergebe dann druckt der mir ja 1,3,4,2 1,4,3,2 usw bis alle durch sind. Wie schaffe ich es jetzt Code-technisch, dass er mir nur 1,2,3,4 und 4,3,2,1 ausgibt und den Rest nicht? Ich kriege es Codetechnisch nicht hin dass er mir nur die sortierten Arrays ausgibt sondern nur dass er mir alle ausgibt. Meine Frage: Wie kann ich das Codetechnisch lösen?

 

[KonradN]

Also mein Code kann ja die Permutationen ausgeben. Das heisst wenn ich 1,2,3,4 übergebe dann druckt der mir ja 1,3,4,2 1,4,3,2 usw bis alle durch sind. Wie schaffe ich es jetzt Code-technisch, dass er mir nur 1,2,3,4 und 4,3,2,1 ausgibt und den Rest nicht? Ich kriege es Codetechnisch nicht hin dass er mir nur die sortierten Arrays ausgibt sondern nur dass er mir alle ausgibt. Meine Frage: Wie kann ich das Codetechnisch lösen?

In dem Du es erst einmal beschreibst. Kannst Du mir sagen, was ich machen soll? Ich soll ja ganz offensichtlich nicht jede Permutation ausgeben. Du musst also da vermutlich irgendwie eingreifen ...

Also eine mögliche Idee wäre hier z.B.:
Für jede Permutation:
- Tritt dem Lehrer in den A.....
- Wenn der Lehrer laut schreit, dann gib die Permutation aus

Ok, das scheint die Aufgabe nicht zu erfüllen. Vielleicht hast Du eine bessere Idee?

 

[Jw456]

Hallo Tipp
vielleicht erst Array Sortieren und dann ausgeben.
Da für gibt es auch Methoden die das können

wenn du das sortieren selber machen willst dann schaue mal im Netzt unter Bubblesort

 

[KonradN]

Hallo Tipp
vielleicht erst Array Sortieren und dann ausgeben.
Da für gibt es auch Methoden die das können

Das ist nicht die Aufgabe.

 

[Jw456]

Dann muss ich jetzt noch mal fragen für mein Verständnis .

Er du hast also das Array 6,5,1,2,3,8,20,15

Und willst nur 1,2,3 ausgeben die andern nicht weil sie nicht sortiert sind ?

 

[rosima26]

Genau. Also ich möchte quasi alle Permutationen generieren aber nur die sortierten sollen beibehalten werden. Die Aufgabe zerbricht mir echt den Kopf

 

[rosima26]

Erst sortieren dann ausgeben wäre nicht zulässig. @Konrad ich schätze dass ich in der Printmethode überprüfen muss ob das was mir übergeben wird sortiert ist oder nicht und nur in dem Falle wird es dann ausgegeben ..

 

[KonradN]

Erst sortieren dann ausgeben wäre nicht zulässig. @Konrad ich schätze dass ich in der Printmethode überprüfen muss ob das was mir übergeben wird sortiert ist oder nicht und nur in dem Falle wird es dann ausgegeben ..

Nein - lass die print Methode. Die macht genau das, was sie machen soll. Wenn Du eine Methode hast, die print heisst, dann sollte die auch genau und zwar ganz genau und ausschließlich eben dies machen: print.

Was Du haben willst ist doch eine andere Methode: sollPermutationAusgegebenWerden oder so.
Also eine Methode, die etwas prüft:

For each Permutation:
--> if (shouldBePrinted(permutation))
----> print(permutation)

Damit musst Du jetzt nur überlegen, was diese eine, neue Methode machen soll.

 

[rosima26]

Hm ja das macht schon Sinn, habe aber wirklich keine Ahnung wie ich das jetzt anstelle...

 

[KonradN]

Dann überlege Dir, was die Aufgabe bedeutet: "ob das Array geordnet ist"

Du hast da ja auch schon erste Details gebracht über ein Beispiel: "sprich 1,2,3,4,5 oder 5,4,3,2,1"
Was besagen denn diese Beispiele? Kannst Du es in Worte fassen? Was ist bei 1,2,3,4,5? Und was ist bei 5,4,3,2,1?

Du merkst: Du vergisst Java - wir behandeln wirklich nur die fachliche Aufgabe!

 

[rosima26]

Ich könnte oben in die Methode mithilfe einer if Abfrage versuchen, nur sortierte Arrays zu übergeben. Wie das sortiert ist kann man ja mit. dem || Operator bewerkstelligen

 

[KonradN]

Wieso willst Du schon Code schreiben, wenn wir doch noch bei der Problemanalyse sind? Vergiss die Programmierung! Erarbeite immer erst die fachlichen Anforderungen im Detail. Denn daran scheitert es aus meiner Sicht.

Wann soll es gedruckt werden? Wenn es aufsteigend sortiert ist. Oder wenn es absteigend sortiert ist.

sollPermutationGedrucktWerden:
- Ist permutation aufsteigend sortiert? -> Ja zurückgeben.
- Ist permutation absteigend sortiert? -> Ja zurück geben.
- Nein zurück geben.

Damit hätten wir das beschrieben. Jetzt kommen wir zu den "istPermutationAufsteigend" und "istPermutationAbsteigend" - das kann man formulieren (So es nicht klar ist, weil ich so checks schon gemacht habt und das somit vorliegt).

Und damit hat man dann eine Beschreibung, die umgesetzt werden kann.

Das printArr(a); kannst Du dann einfach ersetzen durch if (shouldBePrinted(a)) printArr(a);.

shouldBePrinted kann man einfach schreiben als

static boolean shouldBePrinted(int[] array) {
    if (isAscending(array)) return true;
    if (isDescending(array)) return true;
    return false;
}

Und ein if (bedingung) return true; else return false; ist ein einfaches return bedingung. Daher machen wir daraus ggf. direkt ein:

static boolean shouldBePrinted(int[] array) {
    if (isAscending(array)) return true;
    return isDescending(array);
}

 

[KonradN]

Und an der Stelle einfach noch einmal der Hinweis von @Jw456 kommentiert (Weil ich denke, dass wir hier die Aufgabe soweit gelöst haben): Was er meinte, war nicht die Aufgabe und ich habe es relativ kurz abgetan. Aber aus fachlicher Sicht ist die Chance sehr groß, dass dies natürlich die Lösung ist! Denn wenn Du nur die Aufsteigende und die absteigende Permutation haben willst ist das einfach:
a) Array sortieren -> Lösung 1
b) (sortiertes) Array (aus a) umdrehen -> Lösung 2

Wenn doppelte Zahlen vorhanden sein können und da alle Permutationen gewünscht sind, also 1, 1, 2 und 1, 1, 2 (Beim zweiten sind die beiden 1er getauscht .. ändert natürlich nichts an der Gleichheit der Lösungen 🙂 ), dann wäre das hier Problematik, die man nicht abdeckt. Hier würde jede Lösung nur einmal gezeigt und nicht wie bei der Lösung bei Dir eben mehrfach.

Das ist also einfach mal ein Zeichen, dass man die Fachseite gut durchschauen sollte, ehe man da irgend etwas entwickelt oder Algorithmen ableitet. Die Aufgabe hat aber (so ich es richtig verstanden habe) einfach eine klare Aufgabenbeschreibung mit Lösungsweg der vorgegeben ist (Permutationen bilden und Ausgabe filtern) ohne eben über sowas nachzudenken.

 

[temi]

Jetzt musst du dir noch überlegen, wie du bei einem gegebenen Array vorgehst, um herauszufinden, ob es in einer sortierten Reihenfolge vorliegt.

Du hast also beispielsweise die Werte [ 3, 6, 2, 7, 9 ]. Wie gehst du da vor, um herauszufinden, ob die Werte aufsteigend sind?

EDIT: Ich denke nicht, dass die es die richtige Lösung ist, das Array einfach zu sortieren. Es sollen ja alle Permutationen erstellt werden und anschließend geprüft werden, ob sie auf- oder absteigend sortiert ist.

 

[rosima26]

Ja das stimmt wohl. Klar. @temi naja einfach schauen ob das nächste Element größer bzw kleiner ist. Stehe gerade nur noch etwas auf dem Schlauch wo ich das am besten implementiere. Bin noch neu in der Welt der rekursiven Algorithmen

 

[KonradN]

Bin noch neu in der Welt der rekursiven Algorithmen

Dann ist ja gut, dass es absolut nichts mit Rekursion zu tun hat 🙂

Stehe gerade nur noch etwas auf dem Schlauch wo ich das am besten implementiere.

Bei dem skizzierten Vorgehen / dem Code, den ich gezeigt habe, ist es doch deutlich: Da hatte ich doch u.a. diesen Code gezeigt:

static boolean shouldBePrinted(int[] array) {
    if (isAscending(array)) return true;
    return isDescending(array);
}

Somit sind zwei Methoden zu schreiben: isAscending und isDescending und da gehört es dann rein:

static boolean isAscending(int[] array) {
  // Dein Code ...
}

static boolean isDescending(int[] array) {
  // Dein Code ...
}

Das ist dieses Vorgehen, das gerne als "Divide and conquer" (Teile und herrsche) bezeichnet wird. Ein komplexes Problem wird in mehrere kleine Probleme unterteilt und dadurch wird alles überschaubar.

 

[rosima26]

Vieeelen Dank, habt mich gerettet. Hier noch der Code falls mal wieder jemand dasselbe Problem haben sollte

void printArr(int a[]) {

        for (int k = 0; k < a.length; k++)
            System.out.print(a[k]);
        System.out.println();
    }

    void Permutation(int a[], int size) {

        if (size == 1)
            if (shouldBePrinted(a) == true) printArr(a);

        for (int i = 0; i < size; i++) {

            Permutation(a, size - 1);

            if (size % 2 == 1) {
                int temp = a[0];
                a[0] = a[size - 1];
                a[size - 1] = temp;
            } else {
                int temp = a[i];
                a[i] = a[size - 1];
                a[size - 1] = temp;
            }
        }
    }

    static boolean shouldBePrinted(int[] array) {
        if (isAscending(array))
            return true;
        if (isDescending(array))
            return true;
        return false;
    }

    static boolean isAscending(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1])
                return false;
        }
        return true;
    }

    static boolean isDescending(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            if (array[i] < array[i + 1])
                return false;
        }
        return true;
    }

}

 

[rosima26]

Konrad du bist ne Legende

 

[temi]

Noch eine winzige Kritik: Methodennamen sollten in Java per Konvention mit einem Kleinbuchstaben beginnen und durch ein Verb ausdrücken, was sie tun.

Du solltest also den Namen von Permutation() noch etwas verbessern, z. B. permutateArray() 😉

EDIT: Ach, das ist vermutlich der Konstruktor. Sorry. Dann fragt sich allerdings, warum deine Methoden "static" sind, denn da du ja offenbar Instanzen der Klasse erzeugst, sollte das nicht so sein. Normalerweise sollte es in deinem Programm nur einmal "static" geben und zwar vor der main() Methode.

 

[rosima26]

Wo ist eigentlich das Problem wenn ich das so schreibe?

public static void permSort(int a[]) {
        
        int size = a.length;

        if (size == 1)
            if (shouldBePrinted(a) == true)
                printArr(a);

        for (int i = 0; i < size; i++) {

            size --;
            permSort(a);
            

            if (size % 2 == 1) {
                int temp = a[0];
                a[0] = a[size - 1];
                a[size - 1] = temp;
            } else {
                int temp = a[i];
                a[i] = a[size - 1];
                a[size - 1] = temp;
            }
        }

 

[KonradN]

Spiel es doch einfach einmal durch. Du hast einen rekursiven Aufruf mit einer Abbruchbedingung, die nie eintreten wird.

size setzt du immer auf die Größe des Arrays. Wenn die Länger nicht 1 ist, dann gehst Du in die Schleife um da dann sofort es erneut aufzurufen womit Du dann genau das Gleiche wieder machst.

 

[KonradN]

Daher nur noch einmal der gut gemeinte Rat:
- Überlege Dir immer zuerst den Algorithmus!
- Dazu spielst Du das fachliche immer mit Stift und Papier durch!
- Wenn Du den Ablauf mit Stift und Papier hin bekommen hast, dann beschreibst Du es - in einer Sprache, die Du sehr gut kannst!
- Erst dann - und wirklich dann - setzt Du das beschriebene 1:1 in der Sprache Java um.

Alles Andere führt nur zu Problemen. Und genau das macht jeder. Auch ich mache nichts anderes, wobei ich Stift und Papier weg lassen kann und mit meiner Übung das im Kopf durchspielen kann. Sollte ich damit aber Probleme haben, dann greife ich auch zu genau diesen Hilfsmitteln!

 

[rosima26]

Die länge wird aber ja nach jedem Schleifenaufruf vermindert

 

[rosima26]

Ja das stimmt, damit habe ich noch probleme.. ich versuche immer direkt den Code zu schreiben ohne zu wissen was ich da überhaupt genau schreibe

 

[KonradN]

Die länge wird aber ja nach jedem Schleifenaufruf vermindert

Nein, ein Array hat eine feste Länge und die ist unveränderlich. size ist eine lokale Variable, die direkt als erstes auf die Länge des Arrays gesetzt wird. Und wenn du nach der Zuweisung size ausgibst, dann wirst Du sehen, dass dies immer gleich bleibt.

 

[rosima26]

Wie kann ich das denn umschreiben sodass ich auf die übergabe von size verzichten kann

 

[KonradN]

Wie kann ich das denn umschreiben sodass ich auf die übergabe von size verzichten kann

Da weitere Informationen benötigt werden, ist dies rekursiv so nicht wirklich anders möglich.

Man könnte ggf. das Array immer kopieren um dann ein immer um 1 kleineres Array zu übergeben, aber da würde die Ausgabe nicht funktionieren.

 

[rosima26]

Danke dir 😘