Elemente im Array verschieben

[DrippleTripple]

Hi,

ich möchte gerne eine Methode schreiben bei welcher ich meine Array elemente um eine bestimmte Anzahl verschiebe. Wobei elemente welche über die Länge des Arrays hinaus gehen dann iweder vorne landen.

Also z. Bsp:

a=[1,2,3,4,5,6}

verschiebe um k = 2

b={5,6,1,2,3,4}

irgendwie finde ich keinen passenden einfach mathematischen Ausdruck für diesen Algorithmus.

also jetzt ergibt ja

b[0]=a[4]=Betrag von k-a.length
b[1]=a[5]=Betrag von k-a.length-1
b[2]=a[0]= hier unterbricht ja schon wenn ich weiter mit Beträgen zählen möchte, da ja Betrag von k-6=4 und minus 2 bin ich ja dann bei 2 und was stimmt ja dann nicht...
b[3]=a[1]
b[4]=a[2]
b[5]=a[3]

Stehe also ein weng auf dem schlauch....

 

[maki]

Arrays sind low-level und so gar nicht OO.

In Java nutzt man das Collection Framework und dessen Typen (List, Set, Map), dafür gibt es dann auhc die entsprechenden Methoden, zB. Collections.rotate(..)

 

[DrippleTripple]

das mag sein, verstehen möchte ich es trotzdem. und da ich anfänger bin würde ich mich freuen, wenn mir jemand hier weiter helfen würde.

 

[Marco13]

Ja, das Zaumberwort ist "Rotation". Am einfachsten (aber ineffizient) ist es, den Array n-mal um 1 zu rotieren, d.h. n mal sowas zu machen wie

        int a = array[array.length-1];
        System.arraycopy(array, 0, array, 1, array.length-1);
        array[0] = a;

Noch trivialer (aber auch nicht besonders geschickt) wäre, eine Kopie des Arrays zu erstellen, die "rotiert" zu befüllen, und das ganze dann zurückzukopieren. Das "rotierte" Befüllen wäre dann sowas wie

for (int i=0; i<src.length; i++)
{
    int j = (i+n) % dst.length;
    dst[j] = src[i];
}

Für alles effizientere oder geschicktere müßte man nachdenken ... oder mal TAOCP vom Regal holen - da steht sowas bestimmt drin.

 

[DrippleTripple]

hmmm...

was soll ich vom Regal holen???

sdrc und diese copy funktion ist mir noch völlig unbekannt...

würde dann auch das gehen:

zwei for schleifen.

for (i=1;i<k;i++) {
b=a[a.length-(k-i)]
}
for (i=0;i<a.length-k;i++){
b[k+i]=a
}

total bekloppt denke ich aber passt dass oder komme ich irgendwann an einen wert k der mir das falsche ergebnis ausgibt?

 

[DrippleTripple]

ah wird wahrschienlich nicht gehen, wenn k > a.length ist da ich ja dann einen negativen wert erhalte...

das ist ja scheiße...

hmmm

oder warte wenn k größer a.length ist

dann kann ich doch einfach

a=k%a.length machen oder???

habe ich dann ja das gleiche?

also wenn a.length=6 und k=7 ist dann kommt ja nach 6 verschiebungen j alles auf seinen platz oder?

 

[Civilazi]

oder warte wenn k größer a.length ist

dann kann ich doch einfach

a=k%a.length machen oder???

habe ich dann ja das gleiche?

also wenn a.length=6 und k=7 ist dann kommt ja nach 6 verschiebungen j alles auf seinen platz oder?

Geht auch bei <length . Siehe Post über deinem, da steht doch die Lösung, auf die du grad gekommen bist.

 

[Marco13]

TAOCP kannst du websuchen, "src" und "dst" standen für die beiden Arrays: "src" für "source", das ursprüngliche Array, und "dst" für "destination", das Array, wo die Daten reinkopiert werden sollen. System.arraycopy kann man auch mit einer Schleife nachbauen. Diese For-Schleife würde dann nicht so viele Tricks enthalten - das wichtigste ist die Zeile
int j = (i+n) % dst.length;
oder etwas ausführlicher:
int indexImZielArray = (indexImQuellArray + verschiebung) % array.length;

 

[DrippleTripple]

ach tatsache...

ist mir ja gar nicht aufgefallen!!!

danke!

kommt gleich noch ein versuch von mir!

 

[0x7F800000]

Ich hätte hier folgenden Vorschlag: in-place & O(n)
[highlight=Java]
class _
{
public static int gcd(int a, int b){
return b==0?a:gcd(b,a%b);
}
public static int[] rotate(int[] array, int k){
int gcd=gcd(array.length,k);
int steps=array.length/gcd;

for(int g=0; g<gcd; g++){
int temp=array[g];
for(int s=0, currentIndex=g; s<steps;s++){
currentIndex=(currentIndex+k)%array.length;
int swap=array[currentIndex];
array[currentIndex]=temp;
temp=swap;
}
}

return array;
}
public static void main(String..._){
System.out.println(Arrays.toString(rotate(new int[]{1,2,3,4,5,6}, 4)));
}
}
[/highlight]
Ziemlich lustig, nicht?
Was sagt denn der gute alte Herr Prof. Knuth dazu????:L geht's einfacher?

 

[DrippleTripple]

wer ist Prof. Knuth?

was heißt bei Arrays genau die Syntax :

 

[0x7F800000]

Wiee?? :shock::shock: Knuth ist der Autor von TAOCP!! Und überhaupt ein multitalent und berühmtes Genie, so ein paar namen sollte man doch kennen^^
":" bei arrays wird in for-schleifen verwendet
[highlight=Java]
for(int x:new int[]{1,2,3,4,5,6}){
System.out.println(x);
}
[/highlight]
heißt soviel wie "für jedes x aus {1,2,3,4,5,6} mache dies und das"
Wo hast du das her, das kam hier doch nirgends vor????:L

 

[DrippleTripple]

ja, entschuldigung wollte keinem zur nahe treten...

habe mich aber weiter erkundigt!

The Art of Computer Programming - Wikipedia, the free encyclopedia

 

[DrippleTripple]

was würdet ihr hier empfehlen? also für einen anfänger?

welches band ist sinnvol zu hause zu ahebn?

 

[0x7F800000]

Lass erstmal die Algos in Ruh'
Um Java zu lernen braucht man das zuerstmal nicht.
Das eigentliche Buch hab ich auch nie gelesen, aber der Knuth ist halt einfach irgendwie überall present, es gibt einfach so viel zeug wo er mitgemacht hat...:idea:

 

[Marco13]

Wer "ein bißchen Java Programmieren" will, sollte um TAOCP drumrumkommen. Die Bücher gehen ... etwas mehr in die Tiefe.... kannst dir ja mal ein Probekapitel vom 4. Kapitel ansehen ... http://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz