Algoritmi Python

Ruotare una lista in Python

In questa lezione ruoterai una lista di k posizioni verso destra usando lo slicing.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

Introduzione

Il problema

Ruotare una lista compare nei calendari (a chi tocca), nei buffer circolari, nei trucchi con le immagini e nelle domande da colloquio. Spostare gli elementi un passo alla volta funziona ma è lento; lo slicing lo fa in un passo.

Immaginalo così

Ruotare una lista è come una tavola rotonda dove tutti si spostano di due posti a destra. Le ultime due persone fanno il giro fino ai primi posti, e tutti gli altri mantengono il loro ordine. Ruotare di tutti i posti non cambia niente.

Dalla tavola rotonda al codice
steps %= len(values)🔁 Spostarsi di 7 posti a un tavolo da 5 è come spostarsi di 2
values[-steps:]🚶 Le ultime due persone vanno davanti
values[:-steps]🪑 Tutti gli altri mantengono il loro ordine
+🔗 Falli sedere insieme: [4, 5, 1, 2, 3]
Taglia la lista in due pezzi e scambiali.
In una frase

Ruotare una lista a destra di k sposta i suoi ultimi k elementi davanti mantenendo l'ordine di tutti gli elementi.

Punti chiave

  1. if not values: return [] gestisce una lista vuota, dove % len(values) dividerebbe per zero.
  2. steps %= len(values) fa ricominciare da capo le rotazioni grandi.
  3. values[-steps:] è la coda che va davanti: [4, 5].
  4. values[:-steps] è il resto: [1, 2, 3], e + unisce i due pezzi.

Quando si usa?

  • Turni a rotazione e calendari.
  • Buffer circolari e finestre di dati che scorrono.
  • Domande da colloquio su slicing e modulo.

Quando non serve

  • Ruotare ripetutamente di un passo: collections.deque.rotate lo fa sul posto in modo efficiente.
  • Liste enormi in cui la memoria extra conta: un metodo di inversione sul posto evita la copia.

Guarda come funziona

Fai clic su una casella o sposta il cursore per scegliere un indice. Inserisci o elimina per vedere perché tutti gli elementi successivi devono spostarsi.

Codice di esempio

Esegui codice →
main.py
def rotate_right(values, steps):
    if not values:
        return []
    steps %= len(values)
    return values[-steps:] + values[:-steps]

print(rotate_right([1, 2, 3, 4, 5], 2))
Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

[4, 5, 1, 2, 3]

Spiegazione del codice

Il resto della divisione steps %= len(values) gestisce il caso in cui il numero di passi è maggiore della lunghezza della lista, perché ruotare 7 volte una lista di 5 elementi equivale a ruotarla 2 volte. Gli slicing values[-steps:] e values[:-steps] prendono gli ultimi k elementi e il resto, poi li uniscono nel nuovo ordine. La complessità in tempo e in memoria è O(n).

Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.

Esercizi di approfondimento

Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Dimenticare steps uguale a zero

values[-0:] è tutta la lista, quindi senza % il risultato raddoppia.

Problema
return values[-steps:] + values[:-steps]  # steps = 5 gives a list of 10
Correzione
steps %= len(values)
return values[-steps:] + values[:-steps]

Hai finito questa lezione?

Segnala come imparata per tenere traccia dei tuoi progressi.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide