Arrays abwechslend zusammenfügen

[_Paranormal]

Hallo, ich möchte gern eine Methode schreiben, die k-Arrays abwechselnd zusammenfügt.

Also ich habe zum Beispiel:
[2,5,3]
[8,2,5]
[6,9,1]

Und es soll dann zu:
[2,8,5,2,3,5]
[6,9,1]

und zu:
[2,6,8,9,5,1,2,3,5]

werden.


Also, wie man innerhalb eines Arrays tauscht, weiß ich (bubbleSort). Aber wie geht das Array übergreifend?

 

[faetzminator]

Und inwiefern kommst du nicht weiter?
Folgende zwei Tipps sollten weiterhelfen:
Wie lang muss das Ausgabearray sein, welches du am Anfang erstellen musst?
Wie könnte ein 2D Array (alle Arrays in einem Array) und zwei verschachtelte for-Schleifen dir helfen?

Ah ja, was soll denn passieren, wenn ein Array länger ist? Einfach hinten anhängen?

 

[_Paranormal]

Naja, die Arrays am Anfang können beliebig lang sein.

Die for-Schleife könnte ja so aussehen:

for (int i = 0; i < array.length; ++i) {
			for (int j = 0; j < array[i].length; j++) {
						
			array[i][j] = (int) (Math.random() * 30);
				
			}
          }

Und ja, die letzten Elemente sollen einfach angehängt werden

 

[faetzminator]

Und wieso willst du dort drin Math.random() verwenden? Und warum so den Arrays entlang ? Du musst dir die logischen Schritte überlegen.

 

[paraminator]

Um immer nur 2 Arrays zusammenzufügen, werden keine geschachtelten for.Schleifen benötigt. Das Zusammenfügen oben beruht drauf, dass immer nur 2 Arrays zu einer Zeit zusammenfügt werden.

 

[faetzminator]

Ow ja, hab den Output irgendwie anders interpretiert, man sollte genauer lesen

 

[muckelzwerg]

Wie schon gesagt, solltest Du am Anfang die Zielgröße ermitteln und dann ein einziges mal das Zielarray erzeugen.
Und dann brauchst Du einen passenden Durchlauf, um das Array zu befüllen.
Die Anzahl der Schritte sollte der neuen Arraylänge entsprechen.
Einmal durchlaufen und abwechselnd aus den beiden Quellarrays kopieren, klingt doch ganz gut, oder?
Wenn Du die Quellarrays zu einem 2D-Array zusammenfasst (ohne Kopieren) kannst Du sehr angenhem den Indexoperator verwenden.
Dann lässt sich zum Beispiel mit Modulo-Berechnungen sehr leicht Deine gewünschte Kopie machen.
Musst Du aber nicht so machen. Gibt natürlich genug andere schöne Varianten.

 

[_Paranormal]

Jetzt bin ich noch mehr verwirrt.

Ich hab jetzt noch ne Frage. Und zwar weiß ich ja am Anfang nicht, wie viele Arrays ich habe. (Wird erst von der Kommandozeile übergeben.)

Wie übergebe ich das denn am Anfang der Methode?

Also

public void mysort( int [] arrays ) {

Aber da weiß ich ja nicht wie viele Arrays da sind.



Oh, hab den einen Eintrag überlesen. Probiere das mal aus.

 

[faetzminator]

@Muckelzwerg: Wie machst du das bei unterscheidlich langen Arrays?

Also ich würd den Index von 0 bis entweder die Grösse des kleineren oder grösseren Arrays nehmen, der Index des Resultatarrays lässt sich dann ganz einfach folgern ([c]2 * i[/c] bzw [c]2 * i + 1[/c]). Wenn du die Grösse des kleineren Arrays nimmt, musst du nachträglich an die Schleife noch die "überlappenden" Werte des grösseren Arrays kopieren (darfst du [c]System.arraycopy()[/c] verwenden?). Wenn du das grössere Array bevorzugst, musst du einfach jedes Mal gucken, ob denn das kleinere Array genug gross ist und ggf. etwas tricky den Index berechnen (so wie bei Muckelzwergs Vorschlag).

Ich würd also die Iteration über beide Arrays von [c]0 bis [c]Math.min(array1.length, array2.length)[/c] verwenden und danach zwei [c]System.arraycopy()[/c] auszuführen (dann muss man nicht herausfinden, welches das grössere Array ist, und beim kleineren werden dann nur 0 Werte überschrieben).

Edit: halt einfach über alle iterieren:

public static void main(String... args) {
    int[] _1 = { 2, 5, 3 };
    int[] _2 = { 8, 2, 5 };
    int []_3 = { 6,9,1 };
    int[] result = merge(_1, _2, _3);
    System.out.println(Arrays.toString(result));
}

public static int[] merge(int[]... arrays) { // da kann man alle Arrays übergeben
    if (arrays == null || arrays.length == 0) {
        return null;
    }
    // hier muss int[] result erstellt und immer wieder merge() aufgerufen werden
    return result;
}

public static int[] merge(int[] one, int[] other) {
    int result[] = new int[one.length + other.length];
    // deine hauptmethode
    return result;
}

 

[Marcinek]

Ich denke, dass es hier nicht Sinn der Übung ist, dass man die Java API nutzt um eine Aufgabe zu lösen, sondern man soll eher alleine drauf kommen.

 

[faetzminator]

Du meinst das [c]System.arraycopy()[/c]? Natürlich, eine eigene Implementation von [c]arraycopy()[/c] entspricht auch nur einer for-Schleife Aber erstens wärs sinnfrei, dies nachzuprogrammieren (bei einem [c]Arrays.sort()[/c] versteh ichs) und zweitens nicht native

 

[muckelzwerg]

Langsam Leute. Lasst uns doch erstmal sortieren.
Ich sehe jede Menge verschiedene Funktionen.

1) ZWEI Arrays alternierend verknüpfen.
2) bekannte Anzahl mehr als zwei Arrays alternierend verknüpfen
3) unbekannte Anzahl mehr als zwei Arrays alternierend verknüpfen

Das was Du (_Paranormal) im ersten Beitrag zeigst, ist das Nacheinanderausführen von Funktion (1).
Das ist ein anderes Ergebnis, als das direkte Mischen von drei Arrays.
Hier ist also gleich mal die Frage, was es denn nun sein soll.
a1, c1, b1, c2, a2, c3, b2, a3, b3
so wie Du es geschrieben hast oder
a1, b1, c1, a2, b2, c2, a3, b3, c3
das wäre Funktion (2/3).

und dann noch mal alles von vorher mit unterschiedlich langen Arrays. Da ist dann die Frage, was denn überhaupt passieren soll.
Soweit mischen wie möglich und dann nur noch anhängen? Oder den Rest ignorieren? Oder verweigern? ...

 

[faetzminator]

@muckelzwerg:
Wenn man den Text vom TO genau liest, erkennt man es

[2,5,3] (1)
[8,2,5] (2)
[6,9,1] (3)

1 + 2:
[2,8,5,2,3,5] (R1)

R1 + 3:
[2,6,8,9,5,1,2,3,5]

Meine Antworten sind darauf aufbauend - bis auf die erste mit verschachtelten for-Schleifen - was aber nun aufs Gleiche hinausläuft, da ich noch die Methode [c]merge(int[]...)[/c] vorschlage.

 

[muckelzwerg]

"Einfach anhängen" ist noch keine genaue Beschreibung. Schon gar nicht für eine unbekannte Anzahl an Arrays.

Und wenn es nicht um Geschwindigkeit geht, ist es doch mit nur zwei Arrays Popelkram. Dann wird die Funktion zweimal aufgerufen und fertig. Wo ist das Problem?

Wenn man aber alle Arrays in einem Durchlauf mischen will, wird es mit der nicht-alternierenden Variante ziemlich ekelhaft. Selbst bei gleichlangen Arrays.
Deshalb die Frage, ob das überhaupt gewollt ist. a1, c1, b1, c2 ... direkt zu konstruieren ist bei eine ganz andere Hausnummer, als die Funktion zweimal aufzurufen.

 

[faetzminator]

"Einfach anhängen" ist noch keine genaue Beschreibung. Schon gar nicht für eine unbekannte Anzahl an Arrays.

Siehe Beispiellösung von ihm...

Und wenn es nicht um Geschwindigkeit geht, ist es doch mit nur zwei Arrays Popelkram. Dann wird die Funktion zweimal aufgerufen und fertig. Wo ist das Problem?

Vor allem Codeaufwand Ich schreib einfach ungern was, dass es bereits gibt... aber natürlich kann man es auch ausschreiben.

Wenn man aber alle Arrays in einem Durchlauf mischen will, wird es mit der nicht-alternierenden Variante ziemlich ekelhaft. Selbst bei gleichlangen Arrays.
Deshalb die Frage, ob das überhaupt gewollt ist. a1, c1, b1, c2 ... direkt zu konstruieren ist bei eine ganz andere Hausnummer, als die Funktion zweimal aufzurufen.

Und wieder: Siehe Beispiellösung von ihm...
Wenn die Methode gleich mit allen drei Arrays aufgerufen werden würde, dann würde die Lösung so aussehen:
[2,5,3] (1)
[8,2,5] (2)
[6,9,1] (3)

1 + 2 + 3:
[2,8,6,5,2,9,3,5,1]
vgl. mit der Beispiellösung: [2,6,8,9,5,1,2,3,5]

 

[muckelzwerg]

Ich versteh kein Wort. Wieso "würde die Lösung dann so aussehen", wenn es gar nicht die Lösung ist?
Er will nunmal anscheinend keine echt alternierenden Arrays sondern a1, c1, b1, c2 ...
Das sagst Du doch selbst. Warum um alles in der Welt, sollte das Ergebnis dann a1, b1, c1, ... sein, wenn man die Funktion gleich mit drei Arrays aufruft? Das will er doch gerade NICHT, wie es aussieht.

 

[faetzminator]

Lies doch den ersten Post von ihm. Ich will mich nicht nochmal wiederholen

 

[muckelzwerg]

Du redest einfach nur ziemlichen Käse. Sorry. Ob man die Funktion nun mit zwei Arrays zweimal aufruft, oder mit drei Arrays einmal aufruft, ändert nichts am gewünschten Ergebnis.
Wenn sie das nicht liefert, ist die Funktion falsch. Da kann ich nichts für.

 

[faetzminator]

Natürlich kommt es nicht darauf an. Aber man kann theoretisch jedes Beliebige Programm nur in [c]main()[/c] schreiben. Tut ja nichts zur Sache, was die Funktionalität betrifft. Lediglich die Übersichtlichkeit wird erhöht. Warum du in diesem Fall eine Methode zweien vorziehst, versteh ich nicht. Wie dass es der TO genau gestalten will, liegt alleine in seinem Ermessen und ich habe nur eine Idee geliefert, wie man es machen könnte.
Und natürlich liefert mein Beispiel (ausprogrammiert) die von dem TO gewünschte Ausgabe (bzw. Rückgabe von [c]merge(int[]...)[/c]).
Also warte ich nun darauf, dass der TO sich das anschaut und weitere Fragen hat. Eine Diskussion über den schönsten, besten, schnellsten, kompaktesten Code macht an dieser Stelle keinen Sinn mehr.

 

[muckelzwerg]

Wenn die Methode gleich mit allen drei Arrays aufgerufen werden würde, dann würde die Lösung so aussehen:
[2,5,3] (1)
[8,2,5] (2)
[6,9,1] (3)

1 + 2 + 3:
[2,8,6,5,2,9,3,5,1]
vgl. mit der Beispiellösung: [2,6,8,9,5,1,2,3,5]

Das hast Du doch geschrieben? Und das macht einfach keinen Sinn.
Die gewünschte Lösung ist 2, 6, 8, 9, 5, 1, 2, 3, 5. Ob man nun eine Methode hat, die man zweimal anwenden muss, oder eine Methode hat, die das für beliebig viele Arrays in einem Durchgang macht (was deutlich schwerer ist) ändert nichts daran, das sie stimmen muss.

Und ob man das nochmal kapselt oder mit merge(merge(a, b), c) aufruft oder alles in einen block mit zusätzlicher Schleife schreibt, spielt auch keine wirklich Rolle. Die entscheidende Frage ist, wie oft ein neues Array angelegt wird. Und das passiert bei dieser Variante für jeden join, also für jedes zu kombinierende Array. Die schwerere Variante legt nur einmal ein Array mit [a.lenght + b.length + c.length ...] an und kopiert jedes Element nur einmal.

 

[_Paranormal]

Ähm hallo..

Ich versuch es einfach nochmal zu erklären.

Ich frage in der Kommandozeile ab, wie viele Arrays erstellt werden sollen. Dann erstelle ich diese Anzahl (mit beliebigem Inhalt, deswegen das Random..)

Dann soll folgendes gemacht werden.
Beispiel:
Wie viele Arrays?
4

Ausgabe Arrays:
[2,6,4]
[8,1,7,4]
[4,7,2]
[9,5]

Zusammenfügen von erstem und zweitem Array:
[2,8,6,1,4,7,4]

Zusammenfügen von neuem Array und obigem 3. Array:
[2,4,8,7,6,2,1,4,7,4]

Zusammenfügen von neuem Array und obigem 4. Array:
[2,9,4,5,8,7,6,2,1,4,7,4]


Ist das klarer geworden?

 

[muckelzwerg]

Ja. Es war auch vorher schon klar. Nur ob Du es WIRKLICH so willst/haben musst, da war ich mir nicht sicher.
Das sollte ja jetzt nach den ganzen Erklärungen gar kein Problem mehr sein.
faetzminator hat Dir ja sogar schon den Rahmen geschrieben. Du brauchst nur noch den join von zwei Arrays basteln.

 

[_Paranormal]

Ja, ich muss es wirklich so haben

Aber da ihr euch nicht einig wart, hatte ich nochmal genauer beschrieben, wie es aussehen soll.

Erstmal danke

 

[paraminator]

Hier noch etwas komplizierter (um Rekursion zu üben):

public static void fuegeEin(int[] arr1, int i, int[] arr2, 

int[] arr3) {
    if (i < arr1.length) {
        if (i / 2 < arr2.length) {
            arr1[i] = arr2[i / 2];
            fuegeEin(arr1, i + 1, arr3, arr2);
        } else {
            arr1[i] = arr3[i - arr2.length];
            fuegeEin(arr1, i + 1, arr2, arr3);
        }
    }
}

public static void main(String[] args) {

    int[] arr1 = new int[6];
    int[] arr2 = {1, 2};
    int[] arr3 = {3, 4, 5, 6};
    fuegeEin(arr1, 0, arr2, arr3);

    System.out.println(java.util.Arrays.toString(arr1));

}

 

[_Paranormal]

Cool, Danke.

Soweit hab ich das verstanden. Nur eine Frage.
Wieso fügst du in dieser Zeile
[JAVA=20]fuegeEin(arr1, 0, arr2, arr3);[/code]
eine 0 ein?

 

[paraminator]

Naja, weils keine Listen sind, muss es einen Index geben, ab wo eingefügt werden soll/welches Element geändert werden soll.

(das ist ein sich vergrößernder Parameter)

Jetzt kann man sich überlegen, was passieren würde, wenn man die Methode mit irgendwas aufruft. Wenn i nicht negativ ist, gibt es keine Probleme, wenn negativ, dann AIOOBE.
Wenn arr1.length zu kurz, dann keine Probleme, wenn zulang, dann AIOOBE.
Wenn eine Array null, dann sowieso.

Man kann mit Performanceverlust die Methode so modifizieren, dass sie mit jeder Eingabe umgehen kann (besonders effizient ist es ohnehin nicht) oder man schreibt eine zusätzliche Methode, die dann die bisherige aufruft.

 

[_Paranormal]

Ah, danke.

Ich hab jetzt allerdings bei meiner Lösung ein Problem.

import java.util.*;
public class Ha {
	public int[] zipper(ArrayList<int[]> arrays) {
		int k = 0;
		System.out.println("Nächste Stufe:");
		for (int i = 0; i < arrays.size(); i+=2) {
			int l = arrays.get(i).length + arrays.get(i+1).length;
			int[] two = new int[l];
			System.out.print("[");
			if (arrays.get(i).length < arrays.get(i+1).length) {
				k = arrays.get(i+1).length;
			} else {
				k = arrays.get(i).length;
			}
			for (int j = 0; j < k; j++) {
				two[2*j] = arrays.get(i)[j];
				System.out.print(arrays.get(i)[j] + ",");
				two[2*j+1] = arrays.get(i+1)[j];
				System.out.print(arrays.get(i+1)[j] + ",");
			}
			arrays.set(i/2, two);
			arrays.remove(i/2+1);
			System.out.println("]");
		}
		zipper(arrays);
		return arrays.get(0);
	}
}

import java.util.*;
public class Merge {
	public static void main(String[] args) {
		System.out.println("Startarrays:");
		ArrayList<int[]> arrays = new ArrayList<int[]>();
		for (int i = 0; i < 10; i++) {
			int[] a = new int[i+1];
			System.out.print("[");
			for (int j = 0; j < i+1; j++) {
				a[j] = (int)(Math.random()*100);
				System.out.print(a[j] + ",");
			}
			System.out.println("]");
			arrays.add(a);
		}
		int x = 0;
		for (int m = 0; m < arrays.size(); m++) {
			x += arrays.get(m).length;
		}
		int[] result = new int[x];
		result = zipper(arrays);
		System.out.println("Merged!");
	}
}

Hab die beiden Klassen.
Und die Fehlermeldung ist, dass er keine mainclass in Merge finden kann. Ich weiß nicht, wo ich da was falsch gemacht hab. :noe:

 

[paraminator]

Hier ist wieder etwasRekursives:

public static int[] ein(int[]... arrays) {
	if (arrays.length == 2) {
		int[] array = new int[arrays[0].length + arrays[1].length];
		fuegeEin(array, 0, arrays[0], arrays[1]);
		return array;
	}
	int[][] newarrays = new int[arrays.length - 1][];
	for (int i = 0; i < newarrays.length; i++) {
	    newarrays[i] = arrays[i];
	}
	return ein(ein(newarrays), arrays[arrays.length - 1]);
}

iterativ wäre alles viel, viel schneller. idee: Beginne mit einem 0-elementigen Array, füge nacheinander alle anderen Arrays jeweils einzeln hinzu (erstelle ein neues größeres Array und füge Elemente aus beiden Arrays ein).

Wenn man berechnen könnte welches Element an Stelle i im ErgebnisArray vorkommt, ginge es wieder schneller.

Bringt hoffentlich zur Lösung

 

[_Paranormal]

Ne, das bringt mich noch nicht richtig auf die Lösung.

Ich hab das jetzt erstmal zu einer Klasse zusammengefügt, weil er (der Compiler) ja bei 2 gemeckert hat.

import java.util.ArrayList;

public class Ha {
	
	//Erstelle 5 Arrays
	 public static void main(String[] args) {
	        System.out.println("Startarrays:");
	        ArrayList<int[]> arrays = new ArrayList<int[]>();
	        for (int i = 0; i < 5; i++) {
	            int[] a = new int[i+1];
	            System.out.print("[");
	            for (int j = 0; j < i+1; j++) {
	                a[j] = (int)(Math.random()*30);
	                System.out.print(a[j] + ",");
	            }
	            System.out.println("]");
	            arrays.add(a);
	        }
	        int x = 0;
	        for (int m = 0; m < arrays.size(); m++) {
	            x += arrays.get(m).length;
	        }
	        int[] result = new int[x];
	        result = zipper(arrays);
	        System.out.println("Merged!");
	    }


	 
	 public static int[] zipper(ArrayList<int[]> arrays) {
	        int k = 0;
	        System.out.println("Nächste Stufe:");
	        for (int i = 0; i < arrays.size(); i+=2) {
	            int l = arrays.get(i).length + arrays.get(i+1).length;
	            int[] two = new int[l];
	            System.out.print("[");
	            if (arrays.get(i).length < arrays.get(i+1).length) {
	                k = arrays.get(i+1).length;
	            } else {
	                k = arrays.get(i).length;
	            }
	            for (int j = 0; j < k; j++) {
	                two[2*j] = arrays.get(i)[j];
	                System.out.print(arrays.get(i)[j] + ",");
	                two[2*j+1] = arrays.get(i+1)[j];
	                System.out.print(arrays.get(i+1)[j] + ",");
	            }
	            arrays.set(i/2, two);
	            arrays.remove(i/2+1);
	            System.out.println("]");
	        }

	        zipper(arrays);
	        return arrays.get(0);
	}
}

Ich dachte eigentlich ich hätte es relativ gut rekursiv gelöst. Aber ich versteh nicht, wieso ich bei mir nun in Zeile 43 und 24 eine Exception hab..
Kannst du mir da nochmal einen Tipp geben?

 

[paraminator]

Der rekursive Algo sollte dich nicht auf die richtige Lösung bringen, die skizzierte Idee des iterativen Algos allerdings schon.

Ich kann jetzt nicht mir xzeilen Code angucken, ohne das Gehirn zu aktivieren....

Aber was ich vorhin noch auf die Schnelle vorbereitet hatte, sollte weiterhelfen:

		int[] array = new int[arrays[0].length + arrays[1].length];
		int i = 0;
		for (; i / 2 < arrays[0].length && i / 2 < arrays[1].length; i += 2) {
			array[i] = arrays[0][i / 2];
			array[i + 1] = arrays[1][i / 2];
		}
		for (int j = i / 2; j < arrays[0].length; i++, j++) {
			array[i] = arrays[0][j];
		}
		for (int j = i / 2; j < arrays[1].length; i++, j++) {
			array[i] = arrays[1][j];
		}

array: neues zusammengefügtes Array; arrays[0] und arrays[1]: Arrays, die zusammengefügt werden sollen

Das ganze in eine Schleife....

klaaaar?

 

[Marcinek]

Ich sollte so spät keine Beiträge mehr schreiben ;D

Ok in der Liste werden die Arrays dezimiert und durch andere ersetzt ;P

Hilfrech wäre es zu wissen, welche Exception kommt.

Natürlich bezieht sich dieser Beitrag auf den Beitrag von _Paranormal

 

[paraminator]

Beschreibe mal die Aufgabe, wofür du das brauchst un wie dein Kenntnisstand ist.

Es geht doch nicht etwa um Autos im Straßenverkehr, die sich nach dem Reißverschlussprinzip einordnen sollen? Das funktioniert in der Praxis nicht, in der Praxis fährt man bis zum ersten Auto vor und rammt es weg

Vielleicht hast du die Aufgabe auch falsch und es geht nich um Arrays?