Переупорядочение массива на месте?

Ответ 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

Ответ 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. Я называю это "permute from", поскольку значение index[i] указывает, откуда взять i-й элемент результирующей последовательности.

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

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

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

Ответ 3

Если a - массив целых чисел, то возможен O (n) -time, O (1) -пространственный алгоритм, который сохраняет порядок перестановки indices. В этом случае мы можем переместить a в indexes и использовать a в качестве временного хранилища обратной подстановки. После выполнения перестановки массивы a и indices меняются местами, а indices инвертируется in situ с использованием, например, алгоритм 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;
}

Ответ 4

Этот вопрос отвечает на вопрос, когда массив 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 final value already and the original
         // value would have been swapped with src src pos. Keep searching for the
         // original value until it is somewhere ahead of tarInd.
         srcInd = indices[srcInd];
      }
      swap(input, srcInd, tarInd);
   }
}

Ответ 5

Я думаю, что классический способ справиться с этой проблемой состоит в том, чтобы работать вокруг циклов, и для этого вам нужен бит маркера на элемент данных откуда-то. Здесь я ущипнул верхний бит массива индексов, который вы могли бы восстановить - конечно, это предполагает, что у вас нет индексов массива -ve или используются все биты беззнакового числа в качестве индекса. Одной ссылкой для этого является раздел 1.3.3 Knuth Volume 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));
  }
}

Ответ 6

Вы можете сделать это, сокрыв значения в реальном массиве. Таким образом, вы можете сделать это как в 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));
    }
}

Ответ 7

Здесь версия С++ (она изменяет индексы):

#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 }
}

Ответ 8

версия 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);