permute i e T [i]

Question

Supponendo che io abbia una matrice di int T, Sto cercando un algoritmo sul posto che permuta i e T [i]

Ho: [3 2 0 1] (a)

Voglio: [2 3 1 0] (b)

ad es. in (b) T [0] = 2 perché, in (a) T [2] era uguale a 0.

Mi aspettavo di trovare un semplice algoritmo O (n) time, O (1) space, ma non riesco a trovarlo. Qualche idea?

Nota:

• Esiste un array di sigle (a) prima di (b) dopo.

• I valori nella matrice appartengono a [0, N [, nessun duplicato.

Answer 1

Per ottenere l'inversione della permutazione, devi solo percorrere i cicli della permutazione

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

Uso numeri maggiori di N per contrassegnare che fa parte di un ciclo che è già stato elaborato.

Answer 2

Puoi scegliere l'ordinamento lessicografico per ottenere tutte le possibili permutazioni. Segui il link in basso per un elenco di algoritmi di permutazione

Permutazioni

Answer 3

Sembra che tu stia cercando l'inverso nel gruppo di permutazione di un array . La tua matrice di esempio è {0 & # 8594; 3, 1 & # 8594; 2, 2 & # 8594; 0, 3 & # 8594; 1} e vuoi {3 & # 8594; 0, 2 & # 8594; 1, 0 & # 8594; 2, 1 & # 8594; 3}. Riorganizzato, questo è {0 & # 8594; 2, 1 & # 8594; 3, 2 & # 8594; 1, 3 & # 8594; 0} o [2 3 1 0]. Quindi, per trovare l'inverso, devi solo iterare attraverso l'array originale e invertire la mappatura degli indici. Questo dovrebbe funzionare (puoi usare qualsiasi array se conosci la lunghezza):

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

Finché t (con lunghezza n) è una permutazione di [0 .. n-1], tinv non dovrebbe essere indefinito per nessun valore. La soluzione di jpalecek è un po 'più complicata, quindi non sono sicuro che questo sia abbastanza completo per te.

Answer 4

Questo è il mio tentativo di risolvere questo problema sul posto senza memoria aggiuntiva. È un algoritmo O (n).

L'algoritmo di jpalecek è abbastanza intelligente ma non intuitivo da leggere, almeno non per me. L'ho provato e funziona, ma non ho avuto il tempo di capire perché e i commenti sarebbero grandiosi.

L'algoritmo di Gracenotes è eccezionale fintanto che l'array non è troppo grande. Se i dati sono di grandi dimensioni, potrebbe essere necessario creare l'array in modo dinamico.

L'idea di base nel mio algoritmo è quella di aggiornare l'array seguendo la catena di coppie indice e valore. Ad esempio, l'indice 0 viene mappato sul valore 3. Utilizzando il valore 3 come indice, troverete la coppia successiva che è l'indice 3 nell'array e il valore 1. In sostanza, salvo l'indice e la coppia di valori successivi e aggiorno l'indice e il valore di coppia precedenti fino a quando ho finito la catena.

Se riesci a renderlo più efficiente, elegante o migliore nel complesso, sarei interessato.

Ho compilato e testato il codice qui sotto ma non ho usato nessun altro input di test. Ho lasciato l'output di debug per coloro che desiderano provarlo e capire meglio come funziona.

// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
   printf ("%s\n", str_p);
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", i);
   }
   printf ("\n");
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", a[i]);
   }
   printf ("\n\n");
}

// The main code.
void PermuteTheDamnArray()
{
   printArray ("Initial Array", a,n);

   int i = 0;     // Simply a counter.
   int p_ix = 0;  // Previous Index.
   int p_val = a[0]; // Previous Value.
   int n_ix = a[0];  // Next index.
   int n_val = a[n_ix]; // Next Value.
   for (i = 0; i < n; i++)
   {
      // Replace. 
      printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
      a[p_val] = p_ix;

      printArray ("Array after swap", a,n);

      // The next index and value pair becomes the new previous index and value pair.
      p_ix = n_ix;
      p_val = n_val;
      printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);

      // Get the next index and value pair.
      n_ix = n_val;
      n_val = a[n_val];
      printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);

   }

   printArray ("Final Array", a,n);
}



Output:

Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3 
3 2 0 0 

The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3 
3 3 0 0 

The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3 
3 3 1 0 

The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3 
2 3 1 0 

The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3 
2 3 1 0