Алгоритм применения перестановки в пространстве постоянной памяти

Ответ 1

Существует тривиальный алгоритм O (n ^ 2), но вы можете сделать это в O (n). Например:.

A = [a, b, c, d, e]

P = [4, 3, 2, 0, 1]

Мы можем поменять каждый элемент в A на нужный элемент, требуемый P, после каждого подкачки в правой позиции будет еще один элемент и сделать это круговым образом для каждой из позиций ( элементы подкачки, отмеченные с помощью ^ s):

[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4
 ^           ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1
    ^        ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3
    ^     ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step

После одного круга мы найдем следующий элемент в массиве, который не останется в правильном положении, и сделайте это снова. Таким образом, в конце вы получите желаемый результат, и поскольку каждая позиция коснется постоянного времени (для каждой позиции выполняется не более одной операции (своп)), это время O (n).

Вы можете сохранить информацию о том, какой из них находится в нужном месте:

• задайте соответствующую запись в P до -1, которая невосстанавливается: после описанных выше операций P станет [-1, -1, 2, -1, -1], что означает, что только второй может быть не в правильном положении, а еще один шаг будет убедиться, что он находится в правильном положении и завершает алгоритм;

• задайте соответствующую запись в P до -n - 1: P становится [-5, -4, 2, -1, -2], которая может быть восстановлена ​​в O (n) тривиально.

Ответ 2

Еще один ненужный ответ! Это сохраняет явный массив перестановок P, что было необходимо для моей ситуации, но жертвует затратами. Также это не требует отслеживания правильно размещенных элементов. Я понимаю, что предыдущий ответ предоставляет решение O(N), поэтому я думаю, что это просто для развлечения!

Мы получаем лучшую сложность случая O(N), наихудший случай O(N^2) и средний случай O(NlogN). Для больших массивов (N~10000 или больше) средний случай составляет по существу O(N).

Вот основной алгоритм в Java (я имею в виду псевдокод * кашель кашля *)

int ind=0;
float temp=0;

for(int i=0; i<(n-1); i++){
  // get next index
  ind = P[i];
  while(ind<i)
    ind = P[ind];

  // swap elements in array
  temp = A[i];
  A[i] = A[ind];
  A[ind] = temp;
}

Ниже приведен пример работы алгоритма (аналогично предыдущим ответам):

пусть A = [a, b, c, d, e]

и P = [2, 4, 3, 0, 1]

то ожидаемый = [c, e, d, a, b]

i=0:  [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2]
       ^     ^
i=1:  [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4]
          ^        ^
i=2:  [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3]
             ^  ^
i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop...
                ^
i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3
       ?        ^
i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3
             ?  ^
i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3]
                ^
done.

Этот алгоритм может отскакивать в этом цикле while для любых индексов j<i, не более чем на i раз во время итерации ith. В худшем случае (я думаю!) Каждая итерация внешнего цикла for привела бы к дополнительным назначениям i из цикла while, поэтому мы продолжили бы арифметическую серию, которая добавила бы N^2 фактор сложности! Выполнение этого для диапазона N и усреднение числа "дополнительных" назначений, необходимых циклу while (усредненное по многим перестановкам для каждого N, то есть), однако, настоятельно предлагает мне, что средний случай O(NlogN).

Спасибо!

Ответ 3

Просто простой пример добавления кода C/C++ к ответу Ziyao Wei. Код не допускается в комментариях, поэтому в качестве ответа извините

for (int i = 0; i < count; ++i)
{
    // Skip to the next non-processed item
    if (destinations[i] < 0)
        continue;

    int currentPosition = i;

    // destinations[X] = Y means "an item on position Y should be at position X"
    // So we should move an item that is now at position X somewhere
    // else - swap it with item on position Y. Then we have a right
    // item on position X, but the original X-item now on position Y,
    // maybe should be occupied by someone else (an item Z). So we
    // check destinations[Y] = Z and move the X-item further until we got
    // destinations[?] = X which mean that on position ? should be an item
    // from position X - which is exactly the X-item we've been kicking
    // around all this time. Loop closed.
    // 
    // Each permutation has one or more such loops, they obvisouly
    // don't intersect, so we may mark each processed position as such
    // and once the loop is over go further down by an array from
    // position X searching for a non-marked item to start a new loop.
    while (destinations[currentPosition] != i)
    {
        const int target = destinations[currentPosition];

        std::swap(items[currentPosition], items[target]);
        destinations[currentPosition] = -1 - target;

        currentPosition = target;
    }

    // Mark last current position as swapped before moving on
    destinations[currentPosition] = -1 - destinations[currentPosition];
}

for (int i = 0; i < count; ++i)
    destinations[i] = -1 - destinations[i];

(для C - замените std :: swap чем-то другим)

Ответ 4

Таким образом, вы можете поместить нужный элемент в начало массива, работая с оставшимся массивом размера (n-1) на следующем шаге итерации.

Массив перестановки должен быть соответствующим образом настроен так, чтобы отражать уменьшающийся размер массива. А именно, если элемент, который вы разместили в передней части, был найден в позиции "X", вам нужно уменьшить на единицу все индексы, большие или равные X в таблице перестановок.

В случае вашего примера:

array                   permutation -> adjusted permutation

A  =  {[a  b  c  d  e]}                 [4 3 2 0 1]
A1 =  { e [a  b  c  d]}   [3 2 0 1] ->    [3 2 0 1] (decrease all indexes >= 4)
A2 =  { e  d [a  b  c]}     [2 0 1] ->      [2 0 1] (decrease all indexes >= 3)
A3 =  { e  d  c [a  b]}       [0 1] ->        [0 1] (decrease all indexes >= 2)
A4 =  { e  d  c  a [b]}         [1] ->          [0] (decrease all indexes >= 0)

Другой пример:

A0 = {[a  b  c  d  e]}                  [0 2 4 3 1]
A1 = { a [b  c  d  e]}     [2 4 3 1] ->   [1 3 2 0] (decrease all indexes >= 0)
A2 = { a  c [b  d  e]}       [3 2 0] ->     [2 1 0] (decrease all indexes >= 2)
A3 = { a  c  e [b  d]}         [1 0] ->       [1 0] (decrease all indexes >= 2)
A4 = { a  c  e  d [b]}           [0] ->         [0] (decrease all indexes >= 1)

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

Ответ 5

Возвращаемое значение для примера, заданного в начальном вопросе, неверно.

A = [a b c d e]
P = [4 3 2 0 1]

SHOULD return [d e c b a] not as as indicated in the question ([e d c a b])

Ответ 6

Здесь более понятная версия, которая принимает функцию swapElements, которая принимает индексы, например, std::swap(Item[cycle], Item[P[cycle]])$ По существу, она проходит через все элементы и следует циклам, если они не были посетил еще. Вместо второй проверки !visited[P[cycle]], мы также можем сравнить с первым элементом в цикле, который был сделан где-то еще выше.

 bool visited[n] = {0};
 for (int i = 0; i < n; i++)   {
     int cycle = i;
     while(! visited[cycle] && ! visited[P[cycle]]) {
         swapElements(cycle,P[cycle]);
         visited[cycle]=true;
         cycle = P[cycle];
     }
 }

Ответ 7

@RinRisson дал пока единственный правильный ответ! Каждый другой ответ был чем-то, что требовало дополнительной памяти - O (n) стекового пространства или предполагалось, что перестановка P была удобно сохранена рядом с O (n) неиспользованными, но изменяемыми знаковыми битами, или чем-то еще.

Здесь RinRisson правильный ответ выписан в C++. Это проходит каждый тест, который я проводил, включая исчерпывающий тест каждой возможной перестановки длины от 0 до 11.

Обратите внимание, что вам даже не нужна перестановка для материализации; мы можем рассматривать его как полностью черную функцию OldIndex → NewIndex:

template<class RandomIt, class F>
void permute(RandomIt first, RandomIt last, const F& p)
{
    using IndexType = std::decay_t<decltype(p(0))>;

    IndexType n = last - first;
    for (IndexType i = 0; i + 1 < n; ++i) {
        IndexType ind = p(i);
        while (ind < i) {
            ind = p(ind);
        }
        using std::swap;
        swap(*(first + i), *(first + ind));
    }
}

Или добавьте больше интерфейса STL:

template<class RandomIt, class ForwardIt>
void permute(RandomIt first, RandomIt last, ForwardIt pfirst, ForwardIt plast)
{
    assert(std::distance(first, last) == std::distance(pfirst, plast));
    permute(first, last, [&](auto i) { return *std::next(pfirst, i); });
}

Ответ 8

Я согласен со многими решениями здесь, но ниже приведен очень короткий фрагмент кода, который переставляется на протяжении всего цикла перестановок:

def _swap(a, i, j):
    a[i], a[j] = a[j], a[i]


def apply_permutation(a, p):
    idx = 0
    while p[idx] != 0:
        _swap(a, idx, p[idx])
        idx = p[idx]

Итак, фрагмент кода ниже

a = list(range(4))
p = [1, 3, 2, 0]
apply_permutation(a, p)
print(a)

Выходы [2, 4, 3, 1]