[Pseudo-Contest] Mosse per ordinare un array

[Ryuzaki_Eru]

Non sono potuto andare alla PyCon, ma ho visto che il kit comprendeva anche questo problemino:

quale è il minor numero di mosse per ordinare questo array se ad ogni mossa puoi scegliere un qualsiasi elemento e spostarlo in cima o in fondo?

[58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]

Buon divertimento!

[nalsk]

se ho capito bene ogni elemento prelevato fa traslare gli elementi compresi nell'intervallo dalla sua vecchia posizione alla nuova, se si scelgono gli elementi dal massimo al minimo e li si posizionano sempre in testa sono n mosse per avere l'array ordinato. Gli elementi sono 15 quindi 15 mosse.

[Ryuzaki_Eru]

Quando prelevi un elemento non viene traslato nulla, semplicemente gli elementi che vengono dopo o prima l'elemento che prelevi, "scorrono".
Appena tu sposti n/2 elementi, facendo come dici tu, troverai nell'intervallo [0, n/2] i primi n/2 elementi maggiori. Quelli restanti sono i più piccoli e non è detto che devi rispostarli tutti.

[wingman87]

Credo che la soluzione sia trovare la sequenza più lunga di numeri già ordinati tra loro con la restrizione che non possono esserci numeri compresi nei limiti della sequenza all'infuori della sequenza stessa, poi prendere tutti gli altri e spostarli in cima o in fondo similmente a quanto descritto da nalsk.

EDIT:
secondo questo ragionamento la sequenza più lunga è:
29
30
33
35
47
52
Quindi abbiamo 6 numeri già al loro posto, bastano 9 mosse per portare tutti gli altri al posto giusto prima o dopo questa sequenza.

[nalsk]

quoto wingman87 :)

cmq per traslare intendevo proprio lo slittamento, perchè un'altro metodo sarebbe la sostituzione dell'elemento scelto con quello in capo o in coda.
giusto per precisare :)

[Ryuzaki_Eru]

Se sposti e sostituisci alla fine fai due spostamenti ;)

[wingman87]

Se sposti e sostituisci alla fine fai due spostamenti ;)
Non ho capito

[Ryuzaki_Eru]

Non mi riferivo a te.

[B|4KWH|T3]

Quando prelevi un elemento non viene traslato nulla, semplicemente gli elementi che vengono dopo o prima l'elemento che prelevi, "scorrono".
Appena tu sposti n/2 elementi, facendo come dici tu, troverai nell'intervallo [0, n/2] i primi n/2 elementi maggiori. Quelli restanti sono i più piccoli e non è detto che devi rispostarli tutti.


Per come capisco io l'esercizio non c'è nessuno scorrimento

[DanieleC88]

Anche a me vengono 9 mosse, perché se parti da:
[58, 29, 97, 12, 70, 30, 16, 99, 24, 33, 69, 98, 35, 47, 52]
allora puoi spostare in testa alla lista, nell'ordine, il 24, il 16 e il 12, ottenendo:
[12, 16, 24, 58, 29, 97, 70, 30, 99, 33, 69, 98, 35, 47, 52]
a quel punto si possono prendere tutti i numeri che finirebbero dopo il 52 (nell'ordine: 58, 69, 70, 97, 98, 99) e spostarli ordinatamente in coda:
[12, 16, 24, 29, 30, 33, 35, 47, 52, 58, 69, 70, 97, 98, 99]
per un totale di, appunto, 9 mosse.

[Ryuzaki_Eru]

Per come capisco io l'esercizio non c'è nessuno scorrimento

Come no? Quando sposti un elemento quelli che sono successivi scorrono di una posizione.

[B|4KWH|T3]

Non ci può essere scorrimento, lo scorrimento implica uno spostamento non consentito. (tra l'altro teoricamente è anche sbagliato il fatto di contare solo 9 mosse, dato che ogni spostamento alla posizione i+1 è una mossa).

Questa è la mia versione, non ho ancora ben capito la complessità che viene fuori. L'ordinamento è stabile. Probabilmente fa esteticamente schifo, ma non sono un programmatore.

Strumenti: pennarello, lavagna e pseudocodice.


Stupid-Counting-Sort(A):
p <- 1
c <- Count(A,p)
while TRUE:
if c+1>p: // Se è nella posizione sbagliata, allora spostalo
Swap(A[p],A[c+1])
c <- Count(A,1)
else:
while c+1=p: // Se è nella posizione giusta cerca uno nella posizione sbagliata
p <- p+1
c <- Count(A,p)
if c+1!=p:
Swap(A[1],A[p])


Questa funzione conta quanti numeri ci sono inferiori al numero i per calcolare la posizione i in cui spostare il numero.
Count(A,i):
c <- 0:
if A[1]<A[i]:
c <- c+1
return c



E' una modifica del counting sort.
Il concetto è semplicemente di controllare quanti numeri c minori del numero pivot ci sono nell'array e poi scambiare la posizione del numero pivot, con la posizione c+1.
In questo caso il pivot può essere solo la posizione 1 (come nello pseudocodice) o la posizione N.

L'algoritmo si semplificherebbe molto se si potesse usare un secondo array in cui memorizzare quanti numeri ci sono minori del numero i

[B|4KWH|T3]

Come no? Quando sposti un elemento quelli che sono successivi scorrono di una posizione.

E fai tante mosse quanti scorrimenti fai.
La traccia dice che si può fare uno Swap solo con la posizione i e con la posizione N

[B|4KWH|T3]

E poi mi sembrerebbe troppo stupido come esercizio con lo scorrimento

[Ryuzaki_Eru]

Ti stai focalizzando troppo su questo scorrimento, non hai capito di cosa sto parlando. Se hai [1,2,3] e sposti l'1 in fondo, i restanti elementi "scorrono" di una posizione. Il 2 prende il posto dell'1 e il 3 prende il posto del 2. Questo è lo scorrimento e non c'entra niente con lo spostamento di un elemento.
Il tuo algoritmo non l'ho guardato, ma mi sembra inutilmente complicato. Basta fare come è stato già detto precedentemente. Inoltre la funzione Count mi sembra sbagliata, restituisce al massimo c = 1, fa solo un controllo condizionale.

L'algoritmo si semplificherebbe molto se si potesse usare un secondo array in cui memorizzare quanti numeri ci sono minori del numero i

Allora, tralasciando un attimo il testo dell'esercizio, usa un secondo array e poi posta lo pseudocodice e l'esecuzione dell'algoritmo sull'array dell'esercizio.

[B|4KWH|T3]

Ti stai focalizzando troppo su questo scorrimento, non hai capito di cosa sto parlando. Se hai [1,2,3] e sposti l'1 in fondo, i restanti elementi "scorrono" di una posizione. Il 2 prende il posto dell'1 e il 3 prende il posto del 2. Questo è lo scorrimento e non c'entra niente con lo spostamento di un elemento.

No.
Se in un array di n elementi devo spostare l'elemento i in posizione 1, devo spostare tutti gli elementi da 1 ad i-1 di una posizione in avanti.


Il tuo algoritmo non l'ho guardato, ma mi sembra inutilmente complicato. Basta fare come è stato già detto precedentemente. Inoltre la funzione Count mi sembra sbagliata, restituisce al massimo c = 1, fa solo un controllo condizionale.

Sì la funzione Count è sbagliata perchè manca un for.

Allora, tralasciando un attimo il testo dell'esercizio, usa un secondo array e poi posta lo pseudocodice e l'esecuzione dell'algoritmo sull'array dell'esercizio.

Appena ho tempo, correggo quel codice e mostro i passaggi dell'algoritmo punto per punto.

[DanieleC88]

No.
Se in un array di n elementi devo spostare l'elemento i in posizione 1, devo spostare tutti gli elementi da 1 ad i-1 di una posizione in avanti.
Ovvio, ma immagina che siano i nodi di una lista, e non gli elementi di un'array. La cosa diventa fattibilissima. :)
Non c'è nessuno "scorrimento", nella pratica, ma l'effetto è quello.

Comunque, Ryuzaki_Eri, dicci se la soluzione è esatta, se è sbagliata, o almeno dacci un indizio. :p

[B|4KWH|T3]

Ovvio, ma immagina che siano i nodi di una lista, e non gli elementi di un'array. La cosa diventa fattibilissima. :)
Non c'è nessuno "scorrimento", nella pratica, ma l'effetto è quello.

Comunque, Ryuzaki_Eri, dicci se la soluzione è esatta, se è sbagliata, o almeno dacci un indizio. :p


Ovvio, ma c'è scritto che è un array ;)

[DanieleC88]

Trattandosi di PyCon penso che fosse proprio una lista (non esiste un tipo "array" vero e proprio in Python).

[B|4KWH|T3]

Trattandosi di PyCon penso che fosse proprio una lista (non esiste un tipo "array" vero e proprio in Python).

Mi sembrerebbe strano o l'avrebbero chiamata lista. Boh

Cmq c'è anche da chiarire il punto "puoi scegliere un qualsiasi elemento e spostarlo in cima o in fondo". Io lo capisco in modo vincolante, poi boh.

[Ryuzaki_Eru]

Ovvio, ma immagina che siano i nodi di una lista, e non gli elementi di un'array. La cosa diventa fattibilissima. :)
Non c'è nessuno "scorrimento", nella pratica, ma l'effetto è quello.

Ma anche se non lo immagina come una lista l'effetto è quello. Nella pratica non avvine ovviamente, ma concettualmente si.

Comunque, Ryuzaki_Eri, dicci se la soluzione è esatta, se è sbagliata, o almeno dacci un indizio. :p

Non ho la soluzione, ma la mia era pure 9 come *minimo* numero di spostamenti per ordinare l'array.

Mi sembrerebbe strano o l'avrebbero chiamata lista. Boh


Non soffermarti troppo sui nomi. In Python si chiama lista, in C si chiama array di interi. Il concetto è quello.

Cmq c'è anche da chiarire il punto "puoi scegliere un qualsiasi elemento e spostarlo in cima o in fondo". Io lo capisco in modo vincolante, poi boh.

Non c'è niente di vincolante. Hai questo elementi e puoi sceglierne uno qualsiasi e spostarlo o in testa o in coda.

Appena ho tempo, correggo quel codice e mostro i passaggi dell'algoritmo punto per punto.

Bene, sono curioso.

[cionci]

Non soffermarti troppo sui nomi. In Python si chiama lista, in C si chiama array di interi. Il concetto è quello.
Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N) ;)

[DanieleC88]

Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa obbliga ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N) ;)
Sì, ma il "contest" chiedeva appunto quanti fossero gli spostamenti minimi necessari all'ordinamento della lista/array, non si chiedeva quale fosse la complessità asintotica richiesta per farlo. :)

ciao ;)

P.S.: Ryuzaki_Eri, hai raggiunto 666 post, io mi fermerei lì. :Prrr:

[Ryuzaki_Eru]

:eek: :eek: E me lo dici solo ora?? Ecco perchè oggi è stata una giornata d'inferno :asd:

Tra l'altro se fosse una lista, gli spostamenti sono sì gratuiti, ma lo spostamento di un elemento interno alla lista in testa ha un costo nel worst case pari ad O(N) per la ricerca delel'elemento (anche se mediamente è N/2), stessa cosa se si fa il cosiddetto "scorrimento" dell'array (in questo caso il costo è sempre O(N)).
Quindi in definitiva, per lo "scorrimento" che si tratti di un array o di una lista, il costo computazionale è sempre O(N) ;)

Per le liste si, lo spostamento in testa al caso peggiore è O(n), però per l'array il concetto è diverso. Certo, potrebbe essere visto come uno scambio e costerebbe sempre O(n), ma al nostro esercizio non frega nulla della complessità :D

[nalsk]

Ragazzi, dalla traccia dell'esercizio si capisce benissimo che la soluzione è indipendente dai passaggi "fisici" che gli elementi devono subire. Come precisato dalla traccia, una mossa comprende sia la scelta arbitraria dell'elemento sia il suo riposizionamento con annesso scorrimento degli altri elementi. Ovviamente se si va a vedere una possibile implementazione le operazioni da compiersi sono molto più di quelle che ci si aspetta.

[Ryuzaki_Eru]

Ragazzi, dalla traccia dell'esercizio si capisce benissimo che la soluzione è indipendente dai passaggi "fisici" che gli elementi devono subire. Come precisato dalla traccia, una mossa comprende sia la scelta arbitraria dell'elemento sia il suo riposizionamento con annesso scorrimento degli altri elementi. Ovviamente se si va a vedere una possibile implementazione le operazioni da compiersi sono molto più di quelle che ci si aspetta.

Appunto, stiamo dicendo proprio questo.