# Elemente im Array verschieben



## DrippleTripple (19. Mrz 2009)

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 (19. Mrz 2009)

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 (19. Mrz 2009)

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 (19. Mrz 2009)

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 (19. Mrz 2009)

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 (19. Mrz 2009)

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 (19. Mrz 2009)

DrippleTripple hat gesagt.:


> oder warte wenn k größer a.length ist
> 
> dann kann ich doch einfach
> 
> ...



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


----------



## Marco13 (19. Mrz 2009)

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 (19. Mrz 2009)

ach tatsache...

ist mir ja gar nicht aufgefallen!!!

danke!

kommt gleich noch ein versuch von mir!


----------



## 0x7F800000 (19. Mrz 2009)

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 (19. Mrz 2009)

wer ist Prof. Knuth?

was heißt bei Arrays genau die Syntax :


----------



## 0x7F800000 (19. Mrz 2009)

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 (19. Mrz 2009)

ja, entschuldigung wollte keinem zur nahe treten...

habe mich aber weiter erkundigt!

The Art of Computer Programming - Wikipedia, the free encyclopedia


----------



## DrippleTripple (19. Mrz 2009)

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

welches band ist sinnvol zu hause zu ahebn?


----------



## 0x7F800000 (19. Mrz 2009)

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 (19. Mrz 2009)

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


----------

