permute i und T [i]

Question

Unter der Annahme, dass ich ein Array von int T haben, Ich bin für einen In-Place, die permutieren i und T [i]

ich habe: [3 2 0 1] (a)

Ich mag: [2 3 1 0] (b)

zB. in (b) T [0] = 2, da in (a) T [2] gleich 0 ist.

Ich erwarte eine einfache O (n) Zeit zu finden, O (1) Raum-Algorithmus, aber ich kann es nicht finden. Irgendwelche Ideen?

Hinweis:

• Es ist eine Sigel Array (a) vor (b) nach.

• Die Werte im Array gehören zu [0, N [, kein Duplikat.

Answer 1

Um die Umkehrung der Permutation zu erhalten, müssen Sie nur die Zyklen der Permutation haben zu gehen

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;

Ich benutze Zahlen größer als N markieren diese Teil eines Zyklus ist, die bereits verarbeitet wurde.

Answer 2

Sie können für lexikographische Ordnung gehen für alle möglichen Permutationen bekommen. Folgen Sie den Link unten für eine Liste von Permutation Algorithmen

Permutationen

Answer 3

Es scheint, dass Sie für die inverse im Permutationsgruppe eines Arrays suchen . Ihr Beispiel Array ist {0 → 3, 1 → 2, 2 → 0, 3 → 1}, und Sie wollen {3 → 0, 2 → 1, 0 → 2, 1 → 3}. Neu geordnet, das ist {0 → 2, 1 → 3, 2 → 1, 3 → 0} oder [2 3 1 0]. Also, die invers zu finden, müssen Sie nur durch das Original-Array zu durchlaufen und die Zuordnung von Indizes zu umkehren. Dies sollte funktionieren (Sie jedes Array verwenden können, wenn Sie die Länge kennen):

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

Solange t (mit Länge n) eine Permutation von [0 .. n-1], sollte tinv nicht für Werte undefiniert. jpalecek Lösung ist etwas komplizierter, so dass ich bin mir nicht sicher, ob dies für Sie umfassend genug ist.

Answer 4

Dies ist mein Versuch, dieses Problem an Ort und Stelle ohne zusätzliche Speicher zu lösen. Es ist ein O (n) -Algorithmus.

Der Algorithmus von jpalecek ist sehr intelligent, aber nicht intuitiv zu lesen, zumindest nicht für mich. Ich habe es ausprobiert und es funktioniert, aber ich habe nicht die Zeit gehabt, zu verstehen, warum und Kommentare groß sein würden.

Der Algorithmus von Gracenote ist groß, solange das Array nicht zu groß ist. Wenn die Daten groß ist, kann man die Array dynamisch erstellen müssen.

Die Grundidee in meinem Algorithmus ist durch diese Kette von Index-Wert-Paaren des Array zu aktualisieren. Zum Beispiel Index 0 Karten 3. Durch den Wert mit Wert 3 als Index erhalten Sie das nächste Paar finden, den Index 3 in der Anordnung und Wert ist 1. Im Wesentlichen des vorherigen Index und Paarwert das nächste Index-Wert-Paar und aktualisieren wir sparen bis ich die Kette getan.

Wenn Sie es effizienter, elegant oder insgesamt besser machen kann, würde mich interessieren.

Ich habe kompiliert und getestet unter dem Code aber habe keinen anderen Testeingang verwendet. Ich habe für die in der Debug-Ausgabe verlassen, die wünschen, um es auszuprobieren und besser zu verstehen, wie es funktioniert.

// 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