Sposta un array in Java

Lo spostamento di un array può indicare due operazioni diverse. Una rotazione sposta gli elementi in modo circolare e li conserva tutti: una rotazione a destra di due posizioni porta in testa gli ultimi due elementi. La rimozione degli elementi iniziali, invece, restituisce una sequenza più corta e scarta quei valori. Scegli la rotazione se devi conservare il contenuto dell’array; scegli lo scorrimento se vuoi elaborare soltanto il suffisso.

Gli esempi seguenti applicano una rotazione a destra, salvo diversa indicazione. Una distanza positiva ruota a destra, una negativa a sinistra; le distanze maggiori della lunghezza dell’array si possono ridurre usando il modulo rispetto a tale lunghezza. Gli array hanno lunghezza fissa, quindi un metodo che restituisce un nuovo array lascia intatto l’array originale del chiamante soltanto se non lo riassegna né lo modifica.

Gli esempi sono programmi autonomi in Java; l’esempio dell’algoritmo juggling è accompagnato dall’output.

Scegli tra rotazione e rimozione degli elementi iniziali

Se ti serve un array primitivo come int[], usa un ciclo oppure un array temporaneo. Usa Collections.rotate() se i dati sono già in una List o se un array di tipi riferimento può essere trattato come lista. Se devi modificare l’array senza allocarne un altro e accetti un codice più complesso, scegli l’algoritmo juggling. Usa skip() per scartare i primi n elementi di uno stream: non è una rotazione e non conserva la lunghezza originale.

Ruota un array sul posto con un ciclo

Questo metodo esegue uno spostamento a destra alla volta. Prima salva l’ultimo valore, poi sposta a destra gli altri valori e infine colloca quello salvato all’indice zero. L’esempio parte da cinque numeri interi e ruota l’array a destra di due posizioni. Modifica l’array fornito, usa spazio aggiuntivo costante e ha complessità O(n × k), dove n è la lunghezza dell’array e k la distanza normalizzata.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int step = 0; step < steps; step++) {
        int last = values[values.length - 1];
        for (int i = values.length - 1; i > 0; i--) {
          values[i] = values[i - 1];
        }
        values[0] = last;
      }
    }
    System.out.println(Arrays.toString(values));
  }
}

Math.floorMod normalizza le distanze positive e negative in un valore compreso tra zero e uno in meno della lunghezza dell’array. Il controllo della lunghezza evita il modulo per zero e lascia invariato un array vuoto. Anche una distanza normalizzata pari a zero lascia l’array invariato. Questo metodo a spostamenti ripetuti è semplice per distanze piccole; con array o distanze grandi, i due metodi successivi spostano ogni elemento una sola volta.

Ruota usando un array temporaneo

Alloca un secondo array se vuoi una corrispondenza diretta tra indici e puoi usare O(n) spazio aggiuntivo. Per una rotazione a destra, normalizza prima la distanza in steps, così funzionano anche le distanze negative o maggiori della lunghezza. L’elemento che si trova all’indice precedente i passa a ((long) i + steps) % n; il valore intermedio long evita overflow quando si sommano indici int validi. Se l’array è vuoto, ritorna subito prima di calcolare il modulo.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int distance = 2;
    int[] rotated = new int[values.length];
    if (values.length > 0) {
      int steps = Math.floorMod(distance, values.length);
      for (int i = 0; i < values.length; i++) {
        int destination = (int) (((long) i + steps) % values.length);
        rotated[destination] = values[i];
      }
    }
    System.out.println(Arrays.toString(rotated));
  }
}

La formula della destinazione riporta all’inizio gli indici che superano l’ultima posizione. La somma long resta nell’intervallo valido per qualsiasi lunghezza valida di un array Java; il modulo produce quindi una destinazione compresa tra zero e values.length - 1. Sommare lo stesso valore normalizzato steps modulo la lunghezza dell’array definisce una corrispondenza biunivoca: ogni indice di partenza raggiunge una destinazione distinta e l’ordine relativo si conserva. L’array sorgente resta invariato; se vuoi trasferire al nuovo array la responsabilità dei dati, usa quello restituito al posto dell’originale.

Ruota una lista con Collections.rotate()

Collections.rotate() opera su una List: una distanza positiva ruota a destra, mentre una negativa ruota a sinistra. Per un array di tipi riferimento, Arrays.asList(array) crea una lista di dimensione fissa che condivide l’array sottostante: puoi sostituire gli elementi e ruotare la lista, ma non puoi aggiungerne o rimuoverne. Convertire di nuovo la lista in un array crea un array separato. Gli array primitivi come int[] non diventano una List<Integer> tramite Arrays.asList; converti i valori nei corrispondenti wrapper oppure scegli un algoritmo specifico per gli array.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    Integer[] values = {1, 2, 3, 4, 5};
    List<Integer> list = Arrays.asList(values);
    Collections.rotate(list, 2);
    Integer[] rotated = list.toArray(new Integer[0]);
    System.out.println(Arrays.toString(rotated));
  }
}

In questo caso la lista e values condividono gli stessi elementi, quindi la rotazione modifica anche l’ordine nell’array. Anche l’array rotated, creato separatamente, contiene i valori ruotati. È una soluzione concisa per array di oggetti e liste, ma convertire dati primitivi in oggetti wrapper comporta il boxing.

Ruota sul posto con l’algoritmo juggling

L’algoritmo juggling suddivide l’array in cicli. Con una rotazione a sinistra di d posizioni, ogni indice corrente legge l’elemento all’indice current + d, tornando all’inizio quando supera la lunghezza dell’array. Nel codice, calcola l’indice riportato entro i limiti senza rischio di overflow: usa current >= n - d ? current - (n - d) : current + d. Poiché d è normalizzato tra zero e n - 1, il risultato è compreso tra zero e n - 1; se d è zero, l’indice restituito è current. Il numero di cicli indipendenti è gcd(n, d): ciascun ciclo trasporta i valori lungo il proprio percorso fino a tornare all’indice di partenza. Il metodo esegue O(n) spostamenti con O(1) spazio aggiuntivo; può essere utile quando è preferibile evitare l’allocazione di un altro array.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    int rightDistance = 2;
    int n = values.length;
    if (n > 0) {
      int rightSteps = Math.floorMod(rightDistance, n);
      int leftDistance = (n - rightSteps) % n;
      int cycles = gcd(n, leftDistance);
      for (int start = 0; start < cycles; start++) {
        int saved = values[start];
        int current = start;
        while (true) {
          int next = current >= n - leftDistance
              ? current - (n - leftDistance)
              : current + leftDistance;
          if (next == start) break;
          values[current] = values[next];
          current = next;
        }
        values[current] = saved;
      }
    }
    System.out.println(Arrays.toString(values));
  }

  private static int gcd(int a, int b) {
    while (b != 0) {
      int remainder = a % b;
      a = b;
      b = remainder;
    }
    return a;
  }
}

[4, 5, 1, 2, 3]

Il codice normalizza la distanza richiesta verso destra in rightSteps, poi la converte nella distanza equivalente verso sinistra con (n - rightSteps) % n. Per un array di cinque elementi, le distanze verso destra 2 e -2 si normalizzano rispettivamente a due e tre passi; le distanze equivalenti verso sinistra sono quindi tre e due. Anche Integer.MIN_VALUE è gestito correttamente, perché viene normalizzato prima della sottrazione. Una rotazione a sinistra legge l’elemento successivo di ciascun ciclo e, raggiunta la fine dell’array, riparte dall’inizio. Il calcolo condizionale nel codice evita di sommare current e leftDistance quando la somma supererebbe n - 1; in entrambi i rami il risultato resta tra zero e n - 1, anche se la somma senza riporto supererebbe Integer.MAX_VALUE. gcd(n, leftDistance) indica il numero di cicli. Se la distanza normalizzata è zero, gcd(n, 0) vale n e il calcolo condizionale restituisce current, quindi ogni valore viene riscritto senza cambiamenti. Il controllo della lunghezza gestisce un array vuoto prima del calcolo del modulo. I metodi con ciclo e array temporaneo sono più facili da mantenere; scegli juggling quando lo spazio aggiuntivo costante è un requisito concreto.

Salta gli elementi iniziali con la Stream API

Usa skip() quando vuoi omettere i valori iniziali dal risultato, anziché spostarli in fondo. Il metodo restituisce uno stream con gli elementi rimanenti: convertirlo in un array produce un array più corto e non modifica quello sorgente. Se il numero di elementi da saltare è pari o superiore alla lunghezza dello stream, il risultato è vuoto. skip() richiede un conteggio non negativo; se il valore fornito dal chiamante potrebbe essere negativo, convalidalo oppure riportalo a zero.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    int[] values = {1, 2, 3, 4, 5};
    long count = 2;
    int[] remainder = Arrays.stream(values).skip(count).toArray();
    System.out.println(Arrays.toString(remainder));
  }
}

Arrays.stream(values) crea uno stream di interi, skip(count) omette i primi count elementi e toArray() raccoglie quelli rimanenti in un nuovo array primitivo. È comodo per ottenere un suffisso, ma alloca un risultato e non sostituisce la rotazione quando è necessario conservare tutti gli elementi.