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

17

Предположим, что у меня есть массив 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 ?

    
задан dsimcha 09.09.2011 в 20:18
источник
  • В силу того, что он имеет до 2 * n элементов, разве это уже не в O (n) пространстве? Таким образом, вы не увеличиваете сложность пространства, используя третий массив для упрощения. –  corsiKa 09.09.2011 в 22:40
  • @glowcoder: здесь O (1), очевидно, означает, что допускается только постоянное дополнительное пространство. Эквивалентно, алгоритм должен быть на месте. –  Jiri 10.09.2011 в 01:13
  • +1 хорошая проблема –  R.. 11.09.2011 в 22:38

8 ответов

17

С мутированием 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
    
ответ дан QWERTY 09.09.2011 в 20:55
источник
  • Я думаю, что это также O (N ^ 2), потому что во внутреннем цикле ожидаемое время найти точку, где k == i - O (N), и вы делаете O (N) этих циклов. –  dsimcha 09.09.2011 в 21:01
  • @dsimcha: Неверно. Внутренний цикл никогда не будет повторно обрабатывать обработанные альради элементы. По этой причине он не может быть O (N ^ 2). Этот алгоритм делает не более двух проходов над каждым элементом, что делает его O (2N) = O (N). –  AnT 09.09.2011 в 21:06
  • Число раз, когда внутренний цикл «активирован» (т. е. фактически он циклически, в отличие от разрыва) равен числу циклов в перестановке. Каждая «активация» внутреннего цикла делает так много итераций, что есть узлы в цикле. Итак, общее число внутренних итераций всегда равно N, а не N ^ 2. Вот почему этот алгоритм O (N). –  AnT 09.09.2011 в 21:23
  • Итак, мое недоразумение. +1. –  dsimcha 09.09.2011 в 23:07
  • +1 для фактического решения проблемы, в отличие от других ответов, которые просто скрывают обман довольно умеренно. :-) –  R.. 11.09.2011 в 22:35
6

Это то, что я называю алгоритмом «переставить из». В 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-й элемент.

    
ответ дан AnT 09.09.2011 в 21:05
источник
  • В большинстве случаев я не вижу в этом большого смысла, если он разрушает массив индексов, если вам действительно не нужны индексы массива индекса. Если в любом случае это будет память O (N), вы можете просто скопировать его, переставив его. –  dsimcha 09.09.2011 в 21:08
  • Ну, это особенно касается ситуаций, когда впоследствии вам не нужен массив индексов. Я не понимаю ваш аргумент «память». Для версии без места потребуется дополнительная память O (N). Этот алгоритм (при условии, что вы можете пожертвовать содержимым индекса) требует O (1) дополнительной памяти. –  AnT 09.09.2011 в 21:12
  • Правильно, но если вам нужны индексы массива индекса, вам просто нужно скопировать их. –  dsimcha 09.09.2011 в 21:15
  • Обратите внимание, что причина, по которой мы изменяем индекс, - это отметить элементы «уже на месте». Если вы не хотите уничтожать индекс, вы можете повторно реализовать этот алгоритм с дополнительным булевым массивом (который может быть реализован как бит-массив), который используется для обозначения уже обработанных элементов, а не индекса. В этом случае вы можете сохранить индекс неизменным. –  AnT 09.09.2011 в 21:27
  • вам не хватает последних индексов [i_dst] = i_dst; после ожидания [i_dst] =; - иначе вы просто зайдете в бесконечный цикл –  Gregory Pakosz 19.09.2012 в 14:41
Показать остальные комментарии
2

Если 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;
}
    
ответ дан Jiri 09.09.2011 в 23:12
источник
  • +1. Очень интересно и технически отвечает на вопрос, который я задал. Тем не менее, я немного разочарован тем, что он не будет работать, если a - это массив какого-либо типа, кроме целых. –  dsimcha 10.09.2011 в 00:39
  • Это не на месте: индексы [i] = -indices [i] - 1; Предполагается, что по крайней мере один неиспользуемый бит доступен в каждом элементе индексов, т. Е. Он использует O (n) дополнительное пространство. –  R.. 11.09.2011 в 22:34
  • @R .: Алгоритм J, который я называю выше и который я использую, называется «обратным перестановке на месте». Это имя оправдано и принято сообществом. Наша (абстрактная) машина работает с целыми числами, которые могут быть отрицательными. Индексы представляют собой неотрицательные целые числа, хранящиеся в целочисленном типе данных, и, следовательно, могут быть сведены на нет. –  Jiri 11.09.2011 в 23:02
  • Моя абстрактная машина не является JVM и поэтому имеет целые числа без знака. :-) –  R.. 11.09.2011 в 23:08
2

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

Здесь - это решение, когда оно равно not mutable.

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);
   }
}
    
ответ дан Prabu 10.01.2015 в 02:33
источник
1

Я думаю, что классический способ справиться с этой проблемой состоит в том, чтобы работать вокруг циклов, и для этого вам нужен бит маркера на элемент данных откуда-то. Здесь я ущипнул верхний бит массива индексов, который вы могли бы восстановить - конечно, это предполагает, что у вас нет индексов массива -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));
  }
}
    
ответ дан mcdowella 09.09.2011 в 21:26
источник
0

Вы можете сделать это, сокрыв значения в реальном массиве. Таким образом, вы можете сделать это как в 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));
    }
}
    
ответ дан bragboy 09.09.2011 в 21:13
источник
  • Я бы сказал, что этот подход - это O (n) пространство. В теории сложности нет ничего похожего на половину слов. –  Jiri 09.09.2011 в 21:19
  • @Jiri: если вы можете настроить свой алгоритм, например, вместо того, чтобы скрывать это значение в массиве orignial, вы можете скрыть его в массиве индексов. Это не будет наполовину плохим, но в худшем случае потребуется только длина массива. –  bragboy 09.09.2011 в 21:30
0

Вот версия 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 }
}
    
ответ дан Mehrdad 25.03.2013 в 22:56
источник
0

версия 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);    
    
ответ дан mcsheffrey 15.10.2013 в 07:55
источник