Ecco un problema che sto cercando di risolvere per un progetto personale. Non sono esattamente sicuro del modo migliore per affrontarlo.
Problema:
Ho una singola pila già popolata con diverse migliaia di elementi sconosciuti . (Non elementi completamente unici, forse 300 valori diversi. Quindi è una pila con molti duplicati mescolati insieme in un ordine casuale.) Voglio ordinare questi elementi spostandoli tra un numero limitato di altri stack. (Forse tra 10-30 stack al massimo.) Un algoritmo con meno mosse è l'ideale.
Limitazioni:
- Lo stack iniziale è pieno di valori sconosciuti (ad eccezione dell'elemento in alto).
- Posso leggere l'elemento principale in una pila.
- Posso spostare l'elemento superiore di uno stack direttamente in cima a un altro stack.
- Posso verificare se uno stack è vuoto.
- Posso ricordare e memorizzare tutti gli elementi che ho letto e spostato.
In base alle limitazioni di cui sopra, tutti gli elementi devono essere spostati una volta in un altro stack solo in modo che possano essere letti / scansionati. Allora saprei dove e cosa è tutto.
Una volta fatto questo, posso fare il vero ordinamento. (Questa è la parte con cui ho principalmente bisogno di aiuto.) Dopo aver letto e spostato tutti gli elementi una volta, posso quindi calcolare e mettere in coda tutti gli spostamenti di stack necessari per ordinare effettivamente gli elementi.
Presortizzazione e ottimizzazione:
Potrebbe essere troppo presto per pensarci, ma potenzialmente posso fare un pre-ordinamento su stack diversi man mano che gli oggetti vengono letti e spostati.
Ho un'idea generale sulla distribuzione di tutti gli articoli. Ad esempio, se gli elementi sono ordinati alfabeticamente, potrei sapere che i valori degli articoli che iniziano con "S" sono cinque volte più comuni di quelli che iniziano con "V" e che "S" è anche due volte più comune degli oggetti che iniziano con "A" ". Sapere questo è persino utile qui?
Non sono sicuro se ciò sarebbe utile per il pre-ordinamento, ma in alcuni casi potrei anche conoscere tutti i possibili valori degli articoli. Quindi potrei calcolare se il valore di un oggetto è "dispari" o "pari". È possibile eseguire anche altri calcoli simili (come il resto di un'operazione di modulos più grande). Forse separare gli oggetti in pile "dispari" o "pari" renderebbe più facile l'intreccio nelle pile ordinate finali. Sto solo speculando qui, poiché non ho ancora eseguito alcun test.
Risultato desiderato:
Gli articoli non hanno bisogno di essere riordinati in un unico stack, sarebbe probabilmente più ideale se fossero spostati in più pile più piccole di dimensioni uguali. Per esempio, potrei finire con pile ordinate in ordine alfabetico come tali: A-D, D-K, K-R, R-S, S-Z.
Quale tipo di algoritmi sarebbe meglio dare queste limitazioni? Pseudo codice?