HW1bis - esercizio 2

f.cocci (650 points)
1 13 17
asked Feb 27, 2019 in HW1bis by f.cocci (650 points)
Salve a tutti, volevo qualche dritta su come ottimizzare le performance relativamente alla soluzione da me sviluppata per l'esercizio 2 dell' HW1 di recupero.

In pratica:

#inizializzo un contatore a 0

#creo na lista di appoggio uguale ad ls

#finche' il contatore e' minore dell'intero k:

 # inizializzo una variabilire risultato di tipo lista

 # in una range pari alla lunghezza della lista:

  #appendo al risultato l'elemento della lista di appoggio (inizialmente uguale a ls) il cui indice corrisponde all'indice estratto dalla lista lmosse per l'indice i del range di lmosse che stiamo scorrendo.

 #pongo appo uguale al risultato

#incremento il contatore.

Alla fine la funzione una volta arrivato a k-1 esce dal ciclo e ritorna il risultato che e' la lista dopo le k combinazioni.

Il codice funziona perfettamente solo che a partire dal 5 test becco il time-out e non so davvero come ottimizzare.

il problema penso sia ndovuto al fatto che l'operazione venga ripetuta per k volte e dal quinto test k e' davvero grande.

Sto provando a fare ragionamenti su ena eventuale periodicita' del risultato, infatti per la prima coppia di ls e lmosse in pratica a partire dal sesto tentativo che in pratica restituisce il risultato immutato per poi ricominciare a reiterare le stesse combinazioni da 1 a 5.

Grazie, F.
374 views

1 Answer

Best answer
_andrea_ (45670 points)
2 39 297
answered Feb 27, 2019 by _andrea_ (45,670 points)
selected Feb 27, 2019 by f.cocci
Si devi usare la periodicità. Se la lista si ripete dopo 10 volte, e tu devi farlo 1037 volte, ti basta farlo solo 7 volte per ottenere il vero risultato. Ovviamente in realtà devi farlo prima 10 volte (per capire che dopo 10 si ripete) e poi altre 7, quindi 17 in totale, che è diverso sicuramente da 1037. Ovviamente questo è un esempio ma se lo fai il programma ti gira anche il meno di mezzo secondo
f.cocci (650 points)
1 13 17
commented Feb 28, 2019 by f.cocci (650 points)
Finche il risultato generato e' una combinazione diversa di elementi (quindi la sequenza non e' presente tra quelle viste in precedenza) significa che deve continuare a fare il ciclo per generare altri risultati.

Nel momento in cui viene generata una sequenza gia vista, metto il alzo il flag delle variabile STOP e quindi smette di produrre nuovi risultati che da quel momente sarebbere periodici.

Il risultato diventa di volta in volta la tua nuova ls su cui generarne uno nuovo e cosi via.

Facendo un assegnamento non modifichi la lista ls, ma crei una nuova variabili di nome ls.

Alla fine cosi facendo il programma inpiega 0,3 secondi sulla mia macchina a fare tutti i test.
_andrea_ (45670 points)
2 39 297
commented Feb 28, 2019 by _andrea_ (45,670 points)
Non serve un insieme di sequenze, basta vedere se la lista nuova dopo le permutazioni è uguale a quella iniziale per sapere se si è arrivati alla periodicità
f.cocci (650 points)
1 13 17
commented Feb 28, 2019 by f.cocci (650 points)
si anche, perche tornando all'esempio si nota che dopo il sesto tentativo il risultato e' uguale a ls.

Sinceramente, ho visto che funzionava egregiamente e ho chiuso la.
A
AFulvio (220 points)
0 2 5
commented Feb 28, 2019 by AFulvio (220 points)

Scusami F.Cocci ma non capisco ancora un passaggio, una volta controllato se la lista generata è nella lista degli elementi visti, come faccio in caso contrario a continuare ad iterare per le restanti volte ? (Non capisco il passaggio in cui parli di Y, flag e N laugh)

_andrea_ (45670 points)
2 39 297
commented Feb 28, 2019 by _andrea_ (45,670 points)
Esegui gli scambi che rimangono da fare sapendo che dopo n volte la lista torna a posto. Se hai 99 scambi da fare e n=10, devi fare i restanti 9 scambi, che ottieni con modulo