Algoritmo per mischiare

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Algoritmo per mischiare

Messaggio da Lucignolo »

di seguito l'algoritmo che ho sempre usato per mischiare n quantità di variabili
nell'esempio mischio 52 numeri in 208 passaggi..
mi chiedevo se è possibile abbassare il numero di passaggi, ma per ora non trovo soluzione migliore.

'PREPARO VARIABILI
For c = 1 To 52
Numero(c) = c
Next

'MISCHIO CON LO SWAP
conto2 = 0
For c = 1 To 52
x = 1 + Int(Rnd * 52)
Memo = Numero(x)
Numero(x) = Numero(c)
Numero(c) = Memo
conto2 = conto2 + 4
Next

'Totale operazioni (conto2): 208

panurgo
Livello 9
Livello 9
Messaggi: 1326
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Algoritmo per mischiare

Messaggio da panurgo »

se tu usi R il comando

Codice: Seleziona tutto

x <- sample(52)
produce una permutazione "a caso" dei numeri da $1$ a $52$: es.

Codice: Seleziona tutto

x <- sample(52)
print(x)
 [1] 44 29 38 43 37 35  2 12 26 14 52 34 49 18  1 13  5 30 48 42 40 31 28 19 41 24 17 10  7 22  9 23 36 21 39 11  4  3 20 32 25 51  6 16 50 45 46 27 47 15 33  8
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

vabbè ma immagino che al suo interno ci sia un codice che a sua volta consuma tot di operazioni che non possiamo neppure sapere quante sono

a volte perdo tempo a cercare soluzioni impossibili, ho già desistito :P

Pasquale
Livello 11
Livello 11
Messaggi: 2563
Iscritto il: mer mag 25, 2005 2:14 am

Re: Algoritmo per mischiare

Messaggio da Pasquale »

Se lo scopo è quello di diminuire il numero delle operazioni nel loro complesso, questo è un discorso; se invece è quello di fare una buona mischiata di un doppio mazzo di carte, non starei tanto a guardare quante sono le operazioni, se il tempo di soluzione del problema è brevissimo, pur se con molte operazioni.

Ad esempio, le 52 carte, con Decimal Basic, le mischierei come segue, ottenendo il risultato in qualche decimo di secondo:

DIM a(52)
RANDOMIZE
FOR m=1 to 52
DO
LET x=1+INT(RND*52)
IF a(x)=0 THEN
LET a(x)=m
EXIT do
END IF
LOOP
PRINT USING "###)":m;
PRINT x
NEXT M
END

Inoltre c'è da considerare che secondo la tipologia dei comandi e dei linguaggi cambiano anche i tempi di elaborazione.
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

sei sopra le 208 operazioni

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

lo scopo è quello di usare la matematica per migliorare le cose

Pasquale
Livello 11
Livello 11
Messaggi: 2563
Iscritto il: mer mag 25, 2005 2:14 am

Re: Algoritmo per mischiare

Messaggio da Pasquale »

Allora Lucignolo, studiare un algoritmo più efficiente di un altro, va bene, è un miglioramento, specie se l'elaborato è complicato e richiede magari ore o giorni di lavoro.
Poi, circa l’uso della matematica per migliorare le cose, il discorso si fa più complicato e ci porterebbe molto lontano, perché le variabili in gioco sono tante e spesso poco note o non condivise.
Entrando nello specifico delle carte da mischiare, direi che l’algoritmo di Panurgo con un solo comando non è da discutere: chi ha studiato quel comando a livello del linguaggio utilizzato, certamente non sarà l’ultimo arrivato ed avrà pur considerato quanto tu stesso dici, relativamente al sottofondo più vicino al linguaggio macchina su cui il comando è costruito.
Certamente i 4 comandi da te evidenziati sono meno di quelli della mia routine, ma la valutazione dell’efficienza e della validità di un algoritmo non può fermarsi solo al conteggio dei comandi, nel cui sottofondo non saprei cosa c’è.
Ad esempio, mi risulta che il ciclo DO-LOOP sia molto efficiente e che un EXITO DO non valga quanto il confronto fra due variabili o quanto un FOR-NEXT.
Direi che il confronto fra due routine andrebbe fatto più sui tempi di esecuzione, piuttosto che sul conteggio dei comandi, per cui ho reiterato per 10.000 volte le due routine ed ho trovato che la mia ha impiegato 84 centesimi di secondo più della tua, che sembrano meno importanti rispetto alla differenza fra 208 e 236, calcolati come media di una reiterazione della routine.
Infine, hai provato a stampare la tua routine più di una volta e mettere a confronto fra loro i risultati dell’operazione?
A me sembra che il risultato sia sempre lo stesso e che nella routine probabilmente manchi un comando relativo alla randomizzazione, ma non ci metto la mano sul fuoco, perché per poter eseguire la tua routine ho dovuto farlo col mio Decimal Basic e non so se questo abbia cambiato qualcosa.
In linea di massima i linguaggi Basic hanno un comando del tipo RANDOMIZE o RANDOMIZE TIMER o altro similare, basto sull’’orologio del computer, senza del quale ogni volta la casualità non è più casuale..

Comunque, anche da questi confronti utili e costruttivi emerge il pregio di Base5., tanto che c’è stato un periodo in cui alcuni insegnanti frequentatori lo consigliavano ai loro alunni. Forse oggi il tempo viene molto di più dedicato all’uso del cellulare. :(
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

si manca il randomize, non ci ho fatto caso a metterlo perchè il mio scopo è solo quello di diminuire le operazioni
è un puro gioco di ottimizzazione del codice, una sfida con me stesso
ho fatto tante valutazioni ho valutato il risultato della mischiata perfetta da 208 operazioni ( task o token non ricordo il termine esatto )
ho provato a trasformare tutti i 52 numeri in una sola stringa e tramite il random spezzarla e riunirla nei punti esatti
ho provato a diminuire il numero di pescaggi per lo swap, ,le carte si mischiano ugualmente, ma non con la stessa efficienza
ho scoperto che esistono anche due altri modi per scambiare il contenuto di due variabili senza usarne una terza temporanea, ma richiede sempre tre operazioni
ho scoperto che la mischiata swap lascia solo da 0 a 1 carta nella medesima posizione iniziale, e questo mi pare uno degli obiettivi base da raggiungere qualunque sia il sistema usato

dopo 3-4 giorni ho trovato un sistema che mi mischia le carte rispettando tutte le considerazione della premessa con una media di 160 operazioni senza utilizzare lo swap con tre passaggi, e partendo sempre da una base ordinata: a(1)=1, a(2)=2 .... a(52)=52

quanti appassionati di basic o programmazione ci sono nel forum?

Info
Livello 5
Livello 5
Messaggi: 355
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Re: Algoritmo per mischiare

Messaggio da Info »

invertire le variabili Lucignolo, lo fai semplicemente con una somma e due sottrazioni

int a=5, b=3; //a=5, b=3
a=a+b; //a=8, b=3
b=a-b; //a=8, b=5
a=a-b; //a=3, b=5

con due funzioni inverse qualsiasi….
che siano anche una moltiplicazione e due divisioni,
o una potenza e due radici in base n
o con 3 logaritmi….

chiaramente poi diventano troppo lunghe per le risorse da utilizzare….
ma quella con i logaritmi mi ha sempre preso interesse…. ((((-;
usa quella che preferisci
Fai sorridere il tuo HD diventando opensource oriented, scopri come

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

w la matematica

Pasquale
Livello 11
Livello 11
Messaggi: 2563
Iscritto il: mer mag 25, 2005 2:14 am

Re: Algoritmo per mischiare

Messaggio da Pasquale »

OK. da considare pure che nel basic di Decimal Basic, il comando SWAP è implementato esplicitamente, proprio con il comando SWAP


Ad esempio, nella precedente routine, invece di scrivere

Memo = Numero(x)
Numero(x) = Numero(c)
Numero(c) = Memo

sarebbe stato sufficiente scrivere:

SWAP numero(x), numero(c) o anche SWAP numero(c), numero(x)

Certamente, nel sottofondo esisterà comunque una terza variabile provvisoria in cui appoggiare provvisoriamente una delle due da scambiare, ma questo avverrà in modo più veloce e comunque ti consente di risparmiare la tastiera
_________________

\text {     }ciao Immagine ciao
E' la somma che fa il totale (Totò)

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

infatti è impossibile swappare senza una fare almeno tre operazioni con o senza ausilio di una terza variabile...

Info
Livello 5
Livello 5
Messaggi: 355
Iscritto il: lun nov 21, 2005 1:11 pm
Contatta:

Re: Algoritmo per mischiare

Messaggio da Info »

a=log_a(b)
b=b^(1/a)
a=b^a

questa la sequenza piu interessante.... come dicevo prima ((((-;
Fai sorridere il tuo HD diventando opensource oriented, scopri come

Lucignolo
Livello 4
Livello 4
Messaggi: 169
Iscritto il: mar apr 14, 2020 8:47 am

Re: Algoritmo per mischiare

Messaggio da Lucignolo »

secondo me è più interessante questa:

X = X XOR Y
Y = Y XOR X
X = X XOR Y

Rispondi