переставить я и Т [я]

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

Кажется, что вы ищете инверсию в группе перестановок массива. Ваш пример массива: {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 3

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

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

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