переставить i и T[i]

Question

Предполагая, что у меня есть множество Int T, я ищу алгоритм на месте, который проходит I и T [i

У меня есть :[3 2 0 1] (а)

Я хочу :[2 3 1 0] (б)

например.в (b) T[0] = 2, поскольку в (a) T[2] было равно 0.

Я ожидал найти простой алгоритм времени O(n) и пространства O(1), но не смог его найти.Есть идеи ?

Примечание :

• Существует один однозначный массив (a) до (b) после.

• Значения в массиве принадлежат [0, N[, дубликатов нет.

Answer 1

Чтобы получить инверсию перестановки, вам просто нужно пройти циклы перестановки.

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;

Я использую числа больше N, чтобы отметить, что это часть уже обработанного цикла.

Answer 2

Вы можете использовать лексикографический порядок, чтобы получить все возможные перестановки.Перейдите по ссылке ниже, чтобы просмотреть список алгоритмов перестановки.

Перестановки

Answer 3

Кажется, вы ищете обратное в группа перестановок массива.Ваш пример массива: {0→3, 1→2, 2→0, 3→1}, а вам нужен {3→0, 2→1, 0→2, 1→3}.В перестановке это {0→2, 1→3, 2→1, 3→0} или [2 3 1 0].Итак, чтобы найти инверсию, вам просто нужно перебрать исходный массив и перевернуть отображение индексов.Это должно сработать (вы можете использовать любой массив, если знаете длину):

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

Пока t (длиной n) является перестановкой [0 ..n-1],tinv не должен быть неопределенным ни для каких значений.Решение jpalecek несколько сложнее, поэтому я не уверен, что оно достаточно полное для вас.

Answer 4

Это моя попытка решить эту проблему на месте без дополнительной памяти.Это алгоритм O(n).

Алгоритм jpalecek довольно умен, но не интуитивно понятен для чтения, по крайней мере, для меня.Я попробовал это, и это работает, но у меня не было времени понять, почему, и комментарии были бы полезны.

Алгоритм Gracenotes хорош, пока массив не слишком велик.Если данные большие, возможно, придется создать массив динамически.

Основная идея моего алгоритма — обновить массив, следуя цепочке пар индексов и значений.Например, индекс 0 соответствует значению 3.Используя значение 3 в качестве индекса, вы найдете следующую пару: индекс 3 в массиве и значение 1.По сути, я сохраняю следующую пару индекса и значения и обновляю предыдущее значение индекса и пары, пока не завершу цепочку.

Если вы сможете сделать его более эффективным, элегантным или лучше в целом, мне будет интересно.

Я скомпилировал и протестировал приведенный ниже код, но не использовал никаких других тестовых данных.Я оставил отладочный вывод для тех, кто хочет опробовать его и лучше понять, как он работает.

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