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

Question

Допустим, у меня есть массив a длиной n и второй массив indices, также длиной n. indices содержит некоторую произвольную перестановку последовательности [0, n). Я хочу изменить a так, чтобы он был в порядке, указанном indices. Например, используя синтаксис D:

auto a = [8, 6, 7, 5, 3, 0, 9];
auto indices = [3, 6, 2, 4, 0, 1, 5];
reindexInPlace(a, indices);
assert(a == [5, 9, 7, 3, 8, 6, 0]);

Может ли это быть сделано как в O (1) пространстве, так и в O (n) времени, предпочтительно без мутирования indices?

Answer 1

С мутированием indices :(. Без внешнего вида (см. Стабильная сортировка на месте).

a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]

for i in xrange(len(a)):
    x = a[i]
    j = i
    while True:
        k = indices[j]
        indices[j] = j
        if k == i:
            break
        a[j] = a[k]
        j = k
    a[j] = x

print a

Answer 2

Это то, что я называю алгоритмом «перестановки из».В C-подобном языке это будет выглядеть следующим образом:

  for (i_dst_first = 0; i_dst_first < n; ++i_dst_first)
  {
    /* Check if this element needs to be permuted */

    i_src = indices[i_dst_first];
    assert(i_src < n);
    if (i_src == i_dst_first)
      /* This element is already in place */
      continue;

    i_dst = i_dst_first;
    pending = a[i_dst];

    /* Follow the permutation cycle */

    do
    {
      a[i_dst] = a[i_src];
      indices[i_dst] = i_dst;

      i_dst = i_src;
      i_src = indices[i_src];
      assert(i_src != i_dst);

    } while (i_src != i_dst_first);

    a[i_dst] = pending;
    indices[i_dst] = i_dst;
  }

Обратите внимание, что этот алгоритм уничтожает массив index.Я называю это «перестановка из», так как значение index[i] указывает из , где взять i-й элемент результирующей последовательности.

Обратите также внимание, что номер элемента перемещается«Операции, необходимые для перестановки на месте последовательности, равны number of misplaced elements + number of cycles in the permutation.Этот алгоритм достигает этого предела, поэтому с точки зрения количества ходов лучший алгоритм невозможен.

Потенциальная проблема этого алгоритма состоит в том, что он основан на подходе "жонглирования", что делает поведение его кэша далеко от оптимального.Таким образом, хотя этот алгоритм является лучшим в теории, он может проиграть некоторым более «практичным» алгоритмам в реальной жизни.

Можно также реализовать алгоритм «перестановки», где значение index[i] указывает, гдепереместить исходный i-й элемент.

Answer 3

Этот отвечает на вопрос, когда массив indices является изменяемым.

Здесь - решение, когда оно not изменяемое.

void mutate(int[] input, int[] indices) {
   int srcInd;

   for (int tarInd = 0; tarInd < input.length; tarInd++) {
      srcInd = indices[tarInd];
      while(srcInd < tarInd) {

         // when src is behind, it will have it's final value already and the original
         // value would have been swapped with src's src pos. Keep searching for the
         // original value until it is somewhere ahead of tarInd.
         srcInd = indices[srcInd];
      }
      swap(input, srcInd, tarInd);
   }
}

Answer 4

Если a является массивом целых чисел, то возможен O (n) -временный, O (1) -пространственный алгоритм, который сохраняет порядок перестановок indices. В этом случае мы можем переставить a в indexes и использовать a в качестве временного хранилища обратной перестановки. После того как перестановка выполнена, массивы a и indices меняются местами, а indices инвертируется на месте, например, с помощью. алгоритм J от TAoCP . Ниже приведена рабочая программа на Java:

int [] a = {8, 6, 7, 5, 3, 0, 9};
int [] indices = {3, 6, 2, 4, 0, 1, 5};
int n = indices.length;
int i, j, m;    
// permute a and store in indices
// store inverse permutation in a
 for (j = 0; j < n; ++j) {
     i = indices[j]; indices[j] = a[i]; a[i] = j;
 }
 // swap a and indices
 for (j = 0; j < n; ++j) {
     i = indices[j]; indices[j] = a[j]; a[j] = i;
 }
 // inverse indices permutation to get the original
 for (i = 0; i < n; ++i) {indices[i] = -indices[i] - 1;}
 for (m = n - 1; m >= 0; --m) {
     // for (i = m, j = indices[m]; j >= 0; i = j, j = indices[j]) ;
     i = m; j = indices[m]; 
     while (j >= 0) {i = j; j = indices[j];}
     indices[i] = indices[-j - 1];
     indices[-j - 1] = m;
}

Answer 5

Я думаю, что классический способ решения этой проблемы - это обход циклов, и для этого вам понадобится бит маркера для каждого элемента данных откуда-то. Здесь я ущипнул верхний бит массива индекса, который вы могли бы восстановить - конечно, это предполагает, что у вас нет индексов массива -ve или вы используете все биты числа без знака в качестве индекса. Одним из примеров этого является ответ 1.3.3 раздела 1 Кнута на вопрос 12, в котором рассматривается особый случай транспонирования матрицы. Кнут дает ссылки на более медленные методы на месте. В статье Фиха, Манро и Поблете "Перестановка на месте" в худшем случае указывается время и пространство O (1).

import java.util.Arrays;

public class ApplyPerm
{
  public static void reindexInPlace(int[] rearrangeThis, int[] indices) 
  {
    final int TOP_BIT = 0x80000000;
    for (int pos = 0; pos < rearrangeThis.length; pos++)
    {
      if ((indices[pos] & TOP_BIT) != 0)
      { // already dealt with this
        continue;
      }
      if (indices[pos] == pos)
      { // already in place
        continue;
      }
      // Now shift an entire cycle along
      int firstValue = rearrangeThis[pos];
      int currentLocation = pos;
      for (;;)
      {
        // pick up untouched value from here
        int replaceBy = indices[currentLocation];
        // mark as dealt with for the next time we see it
        indices[currentLocation] |= TOP_BIT;
        if (replaceBy == pos)
        { // have worked our way round
          rearrangeThis[currentLocation] = firstValue;
          break;
        }
        if ((replaceBy & TOP_BIT) != 0)
        {
          throw new IllegalArgumentException("Duff permutation");
        }
        // Move value up 
        rearrangeThis[currentLocation] = rearrangeThis[replaceBy];
        // and fill in source of value you have just moved over
        currentLocation = replaceBy;
      }
    }
  }
  public static void main(String[] s)
  {
    int[] a = new int[] {8, 6, 7, 5, 3, 0, 9};
    int[] indices = new int[] {3, 6, 2, 4, 0, 1, 5};
    reindexInPlace(a, indices);
    System.out.println("Result is " + Arrays.toString(a));
  }
}

Answer 6

версия JavaScript

var input = [1,2,3,4,5],
    specArr = [0,2,1,4,3];

function mutate(input, specArr) {

    var visited = [0,2]
    for(var i=0; i<specArr.length; i++) {
        var tmp;

        //keep track of array items we've already looped through (wouldn't want to mutate twice :D)
        visited.push(specArr[i]);
        // if index hasn't changed we do nothing to input arr
        if (visited.indexOf(1) < 0) {
          // if it has changed temporarily store the value
          tmp = input[i];
          //swap input array item with spec item
          input[i] = input[specArr[i]];
          //swap specced array item with input item above
          input[specArr[i]] = tmp;
        }
    }
}

mutate(input, specArr);    

Answer 7

Вот версия C ++ (она изменяет индексы):

#include <algorithm>
#include <iterator>

template<class It, class ItIndices>
void permutate_from(
    It const begin,
    typename std::iterator_traits<It>::difference_type n,
    ItIndices indices)
{
    using std::swap;
    using std::iter_swap;
    for (typename std::iterator_traits<It>::difference_type i = 0; i != n; ++i)
    {
        for (typename std::iterator_traits<ItIndices>::value_type j = i; ; )
        {
            swap(j, indices[j]);
            if (j == i) { break; }
            iter_swap(begin + j, begin + indices[j]);
        }
    }
}

Пример:

int main()
{
    int items[]     = { 2, 0, 1, 3 };
    int indices[]   = { 1, 2, 0, 3 };
    permutate_from(items, 4, indices);
    // Now items[] == { 0, 1, 2, 3 }
}

Answer 8

Вы можете сделать это, скрыв значения в реальном массиве.Таким образом, вы можете сделать это как в O (1) пространстве, так и в O (n) времени.

По сути, сначала вы перемещаетесь по массиву индексов, сохраняя значение массива индексов в правильной позиции.Теперь это можно сделать с помощью выбранного вами алгоритма.Для меня я бы просто сохранил конечные биты числа из позиции «Наиболее значимый бит».Сделайте это за один проход.Теперь базовый массив будет испорчен.

Во время второго обхода сохраните все верхние половины битов в младшую половину.

Очевидным недостатком этого метода является то, что сохраненное целочисленное значениеможет вместить до половины бит.Это означает, что если вы имеете дело с 4-байтовым целым числом, значения могут быть только 2 байта.Однако вместо использования половины массива, как показано в приведенном ниже коде, его можно усовершенствовать, используя лучший алгоритм, в котором вы скрываете значение в индексном массиве.Здесь вам потребуется, чтобы максимальные биты, зарезервированные в худшем случае, были бы длиной массива, а не константой 16 в предыдущем случае.Это будет работать хуже, чем первый, когда длина превышает 2 степени 16.

import java.util.Arrays;
class MyClass {
    public static void main(String[] args) {
        MyClass myClass = new MyClass();
        int[] orig_array = {8, 6, 7, 5, 3, 0, 9};
        int[] indices = {3, 6, 2, 4, 0, 1, 5};
        myClass.meth(orig_array, indices);
    }

    public void meth(int[] orig_array, int[] indices){
        for(int i=0;i<orig_array.length;i++)
            orig_array[i] += orig_array[indices[i]] + orig_array[indices[i]] << 15 ;
        for(int i=0;i<orig_array.length;i++)
            orig_array[i] = orig_array[i] >> 16;
        System.out.print(Arrays.toString(orig_array));
    }
}