Trucco Straordinario#11320

Trucco Straordinario (Editoriale)

Dopo il mescolamento, la $i$ -esima carta da sinistra è la carta $a [p [q [i]]]$ a[p[q[i]]]. Il trucco riesce se per ogni $i$ vale la seguente uguaglianza:

a [p [q [i]]] = i .

a[p[q[i]]] = i.

Denotiamo con $p \circ q$ p \circ q la composizione di permutazioni: $(p \circ q) [i] = p [q [i]]$ (p \circ q)[i] = p[q[i]], cioè prima si applica $q$ e poi $p$ . Sia $I$ la permutazione identica. Allora la condizione del trucco può essere scritta come $a \circ p \circ q = I$ a \circ p \circ q = I.

Applichiamo la permutazione inversa $a^{- 1}$ a^{-1} a entrambi i membri dell'uguaglianza a sinistra, e poi $p^{- 1}$ p^{-1}:

p \circ q = a^{- 1}, q = p^{- 1} \circ a^{- 1} .

p \circ q = a^{-1}, \qquad q = p^{-1} \circ a^{-1}.

Quindi, la permutazione $p$ può essere scelta arbitrariamente, e poi $q$ è determinata in modo univoco: $q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]]. Una permutazione senza punti fissi è detta spostamento (derangement). Il problema si riduce a trovare un derangement $p$ tale che la permutazione $q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1} sia anch'essa un derangement.

Scelta casuale. È impossibile esaminare tutte le $n!$ permutazioni $p$ , quindi scegliamo $p$ a caso:

generiamo una permutazione $p$ casuale; se ha un punto fisso, passiamo al tentativo successivo;
calcoliamo $q = p^{- 1} \circ a^{- 1}$ q = p^{-1} \circ a^{-1};
se $q$ non ha punti fissi, la coppia $(p, q)$ è la risposta.

Effettuiamo al massimo $1000$ tentativi. Se nessuno di essi produce una risposta, stampiamo "Impossible".

Perché funziona. Una risposta non esiste solo in alcuni casi con $n$ piccolo:

$n = 1$ n = 1 — non esistono affatto permutazioni senza punti fissi;
$n = 2$ n = 2 e $a = (2, 1)$ a = (2, 1) — l'unico derangement $p = (2, 1)$ p = (2, 1) dà $q = (1, 2)$ q = (1, 2);
$n = 3$ n = 3 e $a$ scambia esattamente due elementi. Gli unici derangement di lunghezza $3$ sono gli shift ciclici $(2, 3, 1)$ (2, 3, 1) e $(3, 1, 2)$ (3, 1, 2). La composizione di due shift ciclici è di nuovo uno shift ciclico oppure la permutazione identica, quindi non si può ottenere una permutazione che scambia due elementi.

Per $n \geq 4$ n \ge 4, una risposta esiste sempre. Inoltre, come mostra una ricerca esaustiva per $n$ piccoli, la frazione di permutazioni $p$ adatte tra tutte le $n!$ permutazioni è almeno $1/12$ (il minimo si raggiunge per $n = 4$ n = 4), e al crescere di $n$ si avvicina a $1/ e^{2} \approx 0.135$ 1/e^2 \approx 0.135. Pertanto, la probabilità di non trovare una risposta in $1000$ tentativi non supera $(11/12)^{1000} < 1 0^{- 37}$ (11/12)^{1000} < 10^{-37}, che è praticamente zero. Se non esiste alcuna risposta, nessuno dei tentativi avrà successo, e il programma stamperà correttamente "Impossible".

Esempio

Consideriamo il quarto test: $a = (5, 1, 4, 2, 3)$ a = (5, 1, 4, 2, 3).

Troviamo la permutazione inversa: se $a [i] = x$ a[i] = x, allora $a^{- 1} [x] = i$ a^{-1}[x] = i. Poiché $a [1] = 5$ a[1] = 5, $a [2] = 1$ a[2] = 1, $a [3] = 4$ a[3] = 4, $a [4] = 2$ a[4] = 2, $a [5] = 3$ a[5] = 3, otteniamo $a^{- 1} = (2, 4, 5, 3, 1)$ a^{-1} = (2, 4, 5, 3, 1). La figura mostra la permutazione $a$ a sinistra e la sua inversa a destra: tutte le frecce sono invertite.

Generiamo una permutazione casuale $p$ senza punti fissi. Sia, per esempio, $p = (4, 1, 2, 5, 3)$ p = (4, 1, 2, 5, 3). La sua inversa è $p^{- 1} = (2, 3, 5, 1, 4)$ p^{-1} = (2, 3, 5, 1, 4).

Calcoliamo $q [i] = p^{- 1} [a^{- 1} [i]]$ q[i] = p^{-1}[a^{-1}[i]]:

q [1] = p^{- 1} [2] = 3, q [2] = p^{- 1} [4] = 1, q [3] = p^{- 1} [5] = 4, q [4] = p^{- 1} [3] = 5, q [5] = p^{- 1} [1] = 2

q[1] = p^{-1}[2] = 3, \quad q[2] = p^{-1}[4] = 1, \quad q[3] = p^{-1}[5] = 4, \\ q[4] = p^{-1}[3] = 5, \quad q[5] = p^{-1}[1] = 2

Otteniamo $q = (3, 1, 4, 5, 2)$ q = (3, 1, 4, 5, 2). La permutazione $q$ non ha punti fissi, quindi la coppia $(p, q)$ è la risposta. Coincide con la risposta dell'esempio.

Verifichiamo che il trucco riesca, cioè che $a [p [q [i]]] = i$ a[p[q[i]]] = i:

a [p [3]] = a [2] = 1, a [p [1]] = a [4] = 2, a [p [4]] = a [5] = 3, a [p [5]] = a [3] = 4, a [p [2]] = a [1] = 5

a[p[3]] = a[2] = 1, \quad a[p[1]] = a[4] = 2, \quad a[p[4]] = a[5] = 3, \\ a[p[5]] = a[3] = 4, \quad a[p[2]] = a[1] = 5

Nel primo test, $n = 2$ n = 2 e $a = (2, 1)$ a = (2, 1), quindi $a^{- 1} = (2, 1)$ a^{-1} = (2, 1). L'unica permutazione di lunghezza $2$ senza punti fissi è $p = (2, 1)$ p = (2, 1), e $p^{- 1} = (2, 1)$ p^{-1} = (2, 1). Allora $q = p^{- 1} \circ a^{- 1} = (1, 2)$ q = p^{-1} \circ a^{-1} = (1, 2) è la permutazione identica, i cui punti sono tutti fissi. La risposta è "Impossible".

Implementazione dell'algoritmo

La funzione print stampa gli elementi dell'array $a$ , a partire dal primo.

void print(vector<int>& a)
{
  for (int i = 1; i < a.size(); i++)
    printf("%d ", a[i]);
  printf("\n");
}

La funzione is_valid verifica se la permutazione $v$ contiene punti fissi.

bool is_valid(vector<int>& v)
{
  for (int i = 1; i < v.size(); i++)
    if (v[i] == i) return false;
  return true;
}

Dichiariamo gli array.

vector<int> a, p, p1, q;

La parte principale del programma. Leggiamo i dati di input.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Inizializziamo gli array.

  a.resize(n + 1);
  p1.resize(n + 1);
  p.resize(n + 1);
  q.resize(n + 1);

Leggiamo la permutazione di input $a$ e memorizziamo immediatamente la sua inversa nell'array $a$ . Cioè, l'array $a$ contiene la permutazione $a^{- 1}$ a^{-1}, dove $a$ è la permutazione di input.

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

mt19937 è uno dei generatori standard di numeri pseudocasuali in C++ (Mersenne Twister con un periodo di 19937). È molto veloce e ha buone proprietà statistiche, il che lo rende una scelta eccellente per la maggior parte dei compiti che richiedono la generazione di numeri casuali.

  mt19937 gen(random_device{}());

Nella variabile $f o u n d$ , segneremo se per il test corrente è stata trovata una soluzione.

  found = false;

Eseguiamo $1000$ iterazioni.

  for (it = 0; it < 1000; it++)
  {

Generiamo una permutazione casuale. Per farlo, riempiamo l'array $p$ con i numeri $0, 1, 2, ...$ 0, 1, 2, ..., e usiamo la funzione shuffle per mescolare gli elementi, a partire dal primo elemento (non nullo). Lavoriamo con permutazioni da $1$ a $n$ .

    iota(p.begin(), p.end(), 0);
    shuffle(p.begin() + 1, p.end(), gen);

Verifichiamo se la permutazione $p$ è valida (cioè, non contiene punti fissi).

    if (!is_valid(p)) continue;

Calcoliamo la permutazione $p_{1} = p^{- 1}$ p_1 = p^{-1}.

    for (i = 1; i <= n; i++)
      p1[p[i]] = i;

Calcoliamo la permutazione $q = p_{1} ° a^{- 1} = p^{- 1} ° a^{- 1}$ q = p_1 ° a^{-1} = p^{-1} ° a^{-1}.

    for (i = 1; i <= n; i++)
      q[i] = p1[a[i]];

Se la permutazione $q$ è valida, stampiamo il risultato.

    if (is_valid(q))
    {
      puts("Possible");
      print(p);
      print(q);
      found = true;
      break;
    }
  }

C++

Se dopo $1000$ iterazioni non viene trovata alcuna soluzione, allora non esiste alcuna soluzione.

  if (!found) puts("Impossible");
}