Mescolamento casuale#1584

Mescolamento casuale (Editoriale)

Inizialmente abbiamo l'array ${1, 2, ..., n}$ \{1, 2, ..., n\}. Successivamente viene eseguita la procedura di mescolamento. Ci viene data la permutazione finale $A$ . Dobbiamo trovare la probabilità che sia proprio questa quella che otteniamo dopo l'esecuzione della procedura.

La probabilità cercata è uguale a:

\frac{n u m er o d i m o d i p er o tt e n er e A}{n u m er o t o t a l e d i m o d i d i m esco l am e n t o}

\frac{numero~di~modi~per~ottenere~A}{numero~totale~di~modi~di~mescolamento}

Ad ogni passo del mescolamento viene scelto un numero $r$ . Il numero di varianti per la scelta del numero $r$ è uguale a $n$ . Anche il numero di passi del mescolamento è $n$ . Quindi esistono $n^{n}$ n^n sequenze di scelte. Notiamo che sequenze di scelte diverse possono portare alla stessa permutazione finale. Questo perché $n^{n}$ n^n è molto più grande di $n!$ .

Inseriamo nell'array $c u r$ la sequenza ${1, 2, ..., n}$ \{1, 2, ..., n\}. Esamineremo tutte le possibili varianti di scelta $(r_{1}, r_{2}, ..., r_{n})$ (r_1, r_2, ..., r_n), modellando in $c u r$ tutti i possibili processi di mescolamento $(1 \leq r_{i} \leq n)$ (1 \le r_i \le n). Notiamo che una sequenza fissata di numeri $r_{1}, r_{2}, ..., r_{n}$ r_1, r_2, ..., r_n determina univocamente quali scambi verranno eseguiti ad ogni passo, e quindi anche l'array finale dopo il completamento della procedura. Se dopo l'applicazione di tutti gli scambi abbiamo ottenuto l'array $A$ , consideriamo il tentativo riuscito. Supponiamo che tali tentativi risultino essere $s$ . Allora la probabilità cercata è uguale a

s / n^{n}

s / n^n

Implementiamo la funzione shuffle, che effettua l'enumerazione ricorsiva di tutte le possibili continuazioni del processo di mescolamento e conta quante di esse portano alla permutazione obiettivo $А$ .

La funzione ha un parametro $p os$ — il numero dell'iterazione corrente (parte da $0$ ). Questo significa che i primi $p os$ scambi sono già stati eseguiti, e l'array $c u r$ memorizza lo stato ottenuto dopo queste operazioni.

Per rientrare nel limite di tempo, applichiamo il seguente taglio (pruning). Supponiamo che si stia eseguendo l'iterazione con numero $p os$ , e l'array corrente $c u r$ differisca dall'array obiettivo $A$ in $d i f f$ posizioni. Rimangono da eseguire $n - p os$ n - pos scambi. Notiamo che con un solo scambio si possono sistemare al massimo due elementi nelle loro posizioni corrette. Di conseguenza, in totale nei passi rimanenti si possono correggere al massimo $2 \cdot (n - p os)$ 2 \cdot (n - pos) posizioni.

Se invece $d i f f > 2 \cdot (n - p os)$ diff > 2 \cdot (n - pos), allora ottenere da $c u r$ l'array $A$ è già impossibile. In questo caso l'ulteriore enumerazione non ha senso, e il ramo corrente della ricorsione può essere interrotto immediatamente.

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro:

$a$ — la permutazione data $А$ ;
$c u r$ — la permutazione corrente durante l'enumerazione;

int a[10], cur[10];

La funzione shuffle esamina ricorsivamente tutte le possibili continuazioni del processo di mescolamento, contando quante di esse porteranno alla permutazione obiettivo $A$ .

void shuffle(int pos) 
{

Sono state eseguite tutte le $n$ operazioni. Resta da verificare — se l'array ottenuto $c u r$ coincide con quello richiesto $A$ . Se coincide, significa che abbiamo trovato un altro scenario riuscito. In questo caso incrementiamo $co u n tG oo d$ .

  if (pos == n) 
  {
    for (int i = 0; i < n; i++)
      if (cur[i] != a[i]) return;
    countGood++;
    return;
  }

C++

Nella variabile $d i f f$ contiamo in quante posizioni l'array corrente $c u r$ differisce da quello richiesto $A$ .

  int diff = 0;
  for (int i = 0; i < n; i++)
    if (cur[i] != a[i]) diff++;

Al momento ci restano da eseguire $n - p os$ n - pos passi. Con un solo scambio si possono correggere al massimo due posizioni errate. Se già a questo punto le differenze sono maggiori, allora proseguire con la ricorsione non ha senso.

Semplicemente smettiamo di considerare questo ramo dell'enumerazione.

  if (diff > 2 * (n - pos)) return;

Esaminiamo tutti i possibili valori di $r$ .

  for (int r = 0; r < n; r++) 
  {
    swap(cur[pos], cur[r]);
    shuffle(pos + 1);
    swap(cur[pos], cur[r]);
  }
}

C++

Parte principale del programma. Leggiamo il numero $n$ — la dimensione dell'array $А$ .

while (scanf("%d", &n) == 1)
{

Leggiamo l'array di input $А$ . La modellazione inizia sempre con l'array ${1, 2, ..., n}$ \{1, 2, ..., n\}. Lo inseriamo in $c u r$ .

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
    cur[i] = i + 1;
  }

Avviamo l'enumerazione. Nella variabile $co u n tG oo d$ contiamo quante sequenze di scelte casuali porteranno all'array $A$ .

  countGood = 0;
  shuffle(0);

Calcoliamo e stampiamo la risposta.

  res = countGood / pow(n, n);
  printf("%.6lf\n", res);
}