Un altro solitario

[desko]

Anni fa imparai questo solitario, che va avanti in automatico senza che il giocatore debba prendere alcuna decisione, solo stare un po' attento e mi chiedevo qual è la probabilita che riescao, più completamente, quanti mazzetti rimangono alla fine.
Si usa un mazzo da 40 carte (10 per ciascuno dei 4 semi), ma ovviamente è estendibile a qualunque tipo di mazzo.
Si scoprono le carte una alla volta, mettendo l'n-esima a destra dell'(n-1)-esima (la prima ovviament dove ti pare).
Dalla 3ª in poi, dopo averla scoperta si confrontano l'n-esima con la (n-2)-esima e se risultano avere lo stesso seme o lo stesso valore, allora la (n-1)-esima va presa e messa sulla (n-2)esima, facendo scorrere di un posto verso sinistra la n-esima.
Questa sovrapposizione di carte genera dei mazzetti, dei quali interessa esclusiavamente la carta superiore, l'unica visibile (ovvero quante altre e quali altre carte compongono il mazzetto non interessa nulla). Ora, prima di scoprire la carta successiva dal mazzo occorre controllare se la nuova situazione contiene delle coppie di carte in posizioni i e i-2 cha abbiano in comune seme o valore. Si itera questo controllo ed eventuali sovrapposizioni e shftamenti di mazzetti finché è possibile.
Il gioco finisce quando la 40ª carta viene scoperta e si fanno tutte le operazioni conseguenti.
Come esito finale si avrà una serie di mazzetti, da un massimo di 40 da una carta ciascuna, ad un minimo di 2 (da 39 carte quello di sinistra ed 1 quello di destra), che sarebbe l'obiettivo del gioco.
La domanda quindi è: data una permutazione delle 40 carte (il mazzo mescolato all'inizio del gioco), qual è la probabilità che il gioco riesca? o che rimangano 3 mazzetti? o 4? ... 0 40?

Io non so da che parte patire, a parte ridurre i casi per classi di equivalenza, passando da $ 40! $ casi a $ \frac{40!}{10!\cdot 4!} $, calando di 8 ordini di grandezza su 47 i numeri in ballo.

[esempio]
questo 7B 1C 2D 4B 2S
ha come conseguenza quest'altro 7B 1C 4B 2S
da cui quest'ultimo 1C 4B 2S.
Ho messo in evidenza le coppie "sensibili", che causano il cambiamento della fase successiva.
Non che sia importante, ma B sta per bastoni, C per coppe, D per denari e S per spade.
[/esempio]

[Catraga]

E' un problema che e' sorto anche dopo un lauto pasto a Perugia durante un incontro dei borsisti indam dell'ex secondo anno.
La questione e' un ginepraio e siamo solo riusciti a formalizzarlo con l'ausilio delle grammatiche (d'accordo, ci abbiamo pensato anche solo un mezz'oretta... e l'ora dell'abbiocco postprandiale s'avvicinava). Proporrei si spostarlo in matematica non elementare.

[moebius]

Ho paura che questo sarà il nostro "Klondike"! (*)

(*) Nota Storica: Per chi non lo sapesse Klondike è il nome di un popolare solitario (quello di windows per intendersi) che rimane tutt'ora un problema aperto. Nessuno sa con quale probabilità questo riesca; a Las Vegas (e dove altrimenti?) puoi comprare un mazzo di carte per 52$: potete girare una sola volta tutto il mazzo e il banco paga 5$ per ogni carta sistemata. Capite quindi che il calcolo di quante volte possa riuscire in media (la "probabilità" che riesca) è tutt'altro che un fatto di interesse puramente matematico.... Dall'analisi effettuata su situazioni reali (ossia molti, molti, ma molti solitari) pare che riesca con una frequenza di 1/15... Ma questa non è una dimostrazione (in reatà non è nemmeno detto che 1/15 sia la probabilità )

[desko]

Proporrei si spostarlo in matematica non elementare.

non azzecco mai la sezione giusta, non è la prima volta, ma essendo qui da poco non ho ancora capito bene tutto. Mi sembrava un problema combinatorio (ovviamente non elementare), ma questa mi sembrava una sezione più specifica e l'altra più generica.
Comunque, posso spostarlo io o possono solo i moderatori?

Ho paura che questo sarà il nostro "Klondike"!

C'è una differenza: lì c'è discrezionalità, ovvero il giocatore deve effettuare delle scelte; in questo invece può andare tutto in automatico.
Appena imparo a programmare creo un software di simulazione e lo faccio girare tutte le notti, poi vedo la mattina quante sono le vittorie (non è il massimo, ma almeno mi darà un'idea).

[desko]

Sto cercando di buttar giù uno straccio d'algoritmo; per il solitario non ci sono grossi problemi (stasera lo debuggo col mazzo di carte).
Il problema grosso è mischiare le carte, nel senso di creare una permutazione di 40 oggetti.
Cioè, quello che on riesco a rendere è l'estrazione a caso senza reimmissione.

[Catraga]

Non e' la sezione piu' adatta; spero tu stia usando java o c++...
dovresti creare un oggetto ArrayList, costitiuito da 40 oggetti carta con due proprieta', seme e numero, un metodo initialize che inizializza in modo standard le carte, costa 40 iterazioni (2 cicli for annidati, da 4 e da 10), poi un metodo mischia, altre 40 iterazioni dove generi:
0) un mazzo temporaneo
1) numero casuale da 1 a 40
2) pigli la carta corrispondente al numero random uscito, toglila dal mazzo originario e mettila nel mazzo originario, poi il mazzo finale e' costituito, tramite un clone, dal mazzo che hai creato temporaneamente.

[Catraga]

Adesso ho un po' piu' di tempo per risponderti, prima avevo lezione....
In pseudo-Java il codice e' il seguente (uso le convenzioni del Java 1.4)

public class Card
{

private int seme = -1;
private int peso = -1;

public Card(int s, int w)
{
seme = s;
peso = w;
}
public getSeme(){return seme;}
public getPeso(){return peso;}

}

public class Deck
{
private ArrayList mazzo = new ArrayList();

public Deck()
{
for(int i1=0; i1<4; i1++)
{
for(int i2=0; i2<10; i2++)
{
mazzo.add(new Card(i1, i2));}
}
}
}

public shuffle()
{
ArrayList mazzoTemp = new ArrayList();
for(int i=0; i<40; i++)
{
int sel = Random(mazzo.size()); //Questa funzione e' da implementare, ma e' procedura standard.
mazzoTemp(mazzo.get(sel).clone()); //Meglio aggiungere una funzine di cloning all'oggetto carta.
mazzo.remove(sel);
}
mazzo = mazzoTemp.clone(); //Anche questo e' da implementare
}

}

Ed ora hai il mazzo mescolato. La parte dei clones puo' essere modificato, dal momento che la classe non e' composta tramite aggregazione, ovverro ha solo tipi elementari, puoi renderlo cosi':
public shuffle()
{
ArrayList mazzoTemp = new ArrayList();
for(int i=0; i<40; i++)
{
int sel = Random(mazzo.size()); //Questa funzione e' da implementare, ma e' procedura standard.
int s = mazzo.get(sel).getSeme();
int p = mazzo.get(sel).getPeso();
mazzoTemp(new Card(s,p));
mazzo.remove(sel);
}
for(int i=0; i<40; i++)
{
int s = mazzoTemp.get(i).getSeme();
int p = mazzoTemp.get(i).getPeso();
mazzo(new Card(s,p));
}
mazzoTemp.removeAll();
}

[desko]

Grazie mille Catraga.
Io no ho mai usato (e neppure studiato) Java, mentre C++ dovrei conoscerlo, ma ne sono vergognosamente ignorante, ma anche giochini come questo aiutano ad impratichirsi.
Mi sono stampato il codice che hai scritto, così appena ho un po' di tempo cerco di capire meglio l'algoritmo (e magari inizio ad assaggiare Java).
Ma da quel che hai scritto nel messaggio precedente mi par di capire che hai usato un approccio differente da quello che stavo tentando io.

0) un mazzo temporaneo
1) numero casuale da 1 a 40
2) pigli la carta corrispondente al numero random uscito, toglila dal mazzo originario e mettila nel mazzo originario, poi il mazzo finale e' costituito, tramite un clone, dal mazzo che hai creato temporaneamente.

Tu sorteggi la posizione in cui mettere una carta, ma lo fai per le 40 carte? o vai completamente random, ovvero alcune potrebbero essere riposizionate più volte ed altre rimanere ferma? In questo caso fai un numero di riposizionamenti che ritieni sufficiente ad avere un mazzo mescolato?
Poi non capisco quando dici che la togli dal mazzo originario e la metti nel mazzo originario. Diciamo che prendi la carta che si trovava al 23° posto e la rimetti al 15°: devi ar slittare in avanti di uno tutte le carte fra 15° e 22°, giusto?

[Catraga]

No, la cosa e' piu' semplice.
Immagina di avere un mazzo nuovo di zecca e di disporre in fila le carte.
Ora ne scegli a random una, la metti in disparte, ne scegli un'altra a caso e la metti sopra quella che avevi scelto prima, so on... per 40 volte, alla fine hai un mazzo mescolato.

[desko]

No, la cosa e' piu' semplice.
Immagina di avere un mazzo nuovo di zecca e di disporre in fila le carte.
Ora ne scegli a random una, la metti in disparte, ne scegli un'altra a caso e la metti sopra quella che avevi scelto prima, so on... per 40 volte, alla fine hai un mazzo mescolato.

OK, per la prima la scegli con un random fra 1 e 40, ma per le successive? devi sceglierle random fra 1 e 40, ma escludendo i numeri già usciti.

[Catraga]

La struttura dati che andiamo ad utilizzare si chiama lista indiciata, ArrayList e' la classe che la implementa in Java. E' dotata di metofi push (inserisci) e get (restituisci), che non e' un pop (non so a quanto arrivi la tua conoscenza di strutture dati, ma spero che tu riesca a capire). Quando mescolo ad ogni iterazione faccio un get ed un remove, inoltre la carta vado a pescarla con Random(mazzo.size()) che e' un'istruzione dinamica ovvero aggiornata ad ogni iterazione, dal momento che mazzo.size() decrementa di 1 ad ogni chiamata dell'istruzione remove(int k).
Se vuoi te lo spiego via messaggi privati, poiche' stiamo esulando un po' troppo dal topic combinatoria....

[desko]

Mi sto rendendo conto che la mia ignoranza è ancora profonda su queste cose.
Il metodo che descrivi è quello che stavo cercando di fare (per favore non metterti a ridere) con Excel.
Alla carta i-esima associo un numero random fra 1 e 41-i, poi shifto in avanti questo numero in base a quanti sono i numeri minori già usciti. Il problema è che capita che in questo shiftaggio capita che vengano sorpassati dei nuovi numeri già usciti e quindi dovrei rishiftare ma solo dei nuovi sorpassi.
Un gran casino.
Comunque hai ragione: meglio fermarsi qua che andiamo più sull'informatica che sulla combinatoria.
Grazie.

PS: vedo che sei (o solo studi?) di Trieste, io sto a Modena, ma il mio cuore sta lassù insieme alle mie radici.