Возможно ли переставить массив на место в O (N)?

Ответ 1

Я думаю, что это должно сделать:

static <T> void arrange(T[] data, int[] p) {
    boolean[] done = new boolean[p.length];        
    for (int i = 0; i < p.length; i++) {
        if (!done[i]) {
            T t = data[i];
            for (int j = i;;) {
                done[j] = true;

                if (p[j] != i) {
                    data[j] = data[p[j]];
                    j = p[j];
                } else {
                    data[j] = t;
                    break;
                }
            }                
        }
    }
}

Примечание. Это Java. Если вы делаете это на языке без сбора мусора, обязательно удалите done.

Если вам небезразлично, вы можете использовать BitSet для done. Я предполагаю, что вы можете позволить себе дополнительный бит на элемент, потому что вы, похоже, готовы работать с массивом перестановок, который в несколько раз превышает этот размер.

Этот алгоритм копирует экземпляры T n + k раз, где k - количество циклов в перестановке. Вы можете уменьшить это до оптимального количества копий, пропустив те, где p [i] = i.

Ответ 2

Вы имеете в виду, что у вас есть массив объектов O [1..N], а затем у вас есть массив P [1..N], который содержит перестановку чисел 1..N, и в конце вы хотите получить массив O1 таких объектов, что O1 [k] = O [P [k]] для всех k = 1..N?

В качестве примера, если ваши объекты представляют собой буквы A, B, C..., Y, Z и ваш массив P [26,25,24,.., 2,1] - ваш желаемый результат Z, Y,... C, B, A?

Если да, я считаю, что вы можете сделать это в линейном режиме, используя только O (1) дополнительную память. Обратный элемент массива является особым случаем этого сценария. В общем, я думаю, вам нужно будет рассмотреть декомпозицию вашей перестановки P в циклы, а затем использовать ее для перемещения элементов исходного массива O [].

Если это то, что вы ищете, я могу подробнее рассказать.

EDIT: Другие уже представили отличные решения, пока я спал, поэтому нет необходимости повторять его здесь. ^ _ ^

EDIT: мое O (1) дополнительное пространство действительно не совсем корректно. Я думал только об элементах данных, но на самом деле вам также нужно сохранить один бит на элемент перестановки, поэтому, если мы точны, для этого нам нужны O (log n) дополнительные биты. Но большую часть времени, используя знаковый бит (как это предлагает Дж. Ф. Себастьян), хорош, поэтому на практике нам может не понадобиться ничего больше, чем мы уже имеем.

Ответ 3

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

// Pseudo-code
N : integer, N > 0 // N is the number of elements
swaps : integer [0..N]
data[N] : array of object
permute[N] : array of integer [-1..N]  denoting permutation (used element is -1)
next_scan_start : integer;

next_scan_start  = 0;

    while (swaps < N )
    {
        // Search for the next index that is not-yet-permtued.  
        for (idx_cycle_search = next_scan_start; 
             idx_cycle_search < N;
             ++ idx_cycle_search)
            if (permute[idx_cycle_search] >= 0)
                break;

        next_scan_start = idx_cycle_search + 1;

        // This is a provable invariant.  In short, number of non-negative
        // elements in permute[] equals (N - swaps)
        assert( idx_cycle_search < N );

        // Completely permute one permutation cycle, 'following the
        // permutation cycle trail'  This is O(N)
        while (permute[idx_cycle_search] >= 0)
        {
             swap( data[idx_cycle_search], data[permute[idx_cycle_search] )
             swaps ++;

             old_idx = idx_cycle_search;
             idx_cycle_search = permute[idx_cycle_search];
             permute[old_idx] = -1;  
             // Also '= -idx_cycle_search -1' could be used rather than '-1'
             // and would allow reversal of these changes to permute[] array
        }
    }

Ответ 4

Если вы не возражаете выделить память для дополнительного хэша индексов, вы можете сохранить сопоставление исходного местоположения с текущим местоположением, чтобы получить временную сложность около O (n). Вот пример в Ruby, так как он читается и псевдокод-ish. (Это может быть короче или более идиоматично Ruby-ish, но я написал его для ясности.)

#!/usr/bin/ruby

objects       = ['d', 'e', 'a', 'c', 'b']
order         = [2, 4, 3, 0, 1]
cur_locations = {}

order.each_with_index do |orig_location, ordinality|
  # Find the current location of the item.
  cur_location = orig_location
  while not cur_locations[cur_location].nil? do
    cur_location = cur_locations[cur_location]
  end

  # Swap the items and keep track of whatever we swapped forward.
  objects[ordinality], objects[cur_location] = objects[cur_location], objects[ordinality]
  cur_locations[ordinality] = orig_location
end

puts objects.join(' ')

Это, очевидно, связано с некоторой дополнительной памятью для хэша, но поскольку это просто для индексов, а не для ваших "довольно больших" объектов, мы надеемся, что это приемлемо. Поскольку поиск хэшей - это O (1), хотя есть небольшая ошибка в сложности из-за того, что элемент был заменен более чем один раз, и вам нужно переписать cur_location несколько раз, алгоритм в целом должен достаточно близки к O (n).

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

EDIT: На самом деле, я уверен, что сложность времени - это просто O (n), так как каждая нормальность может иметь не более одного связанного перехода, и, следовательно, максимальное количество поисков ограничено n.

Ответ 5

#!/usr/bin/env python

def rearrange(objects, permutation):
    """Rearrange `objects` inplace according to `permutation`.

       ``result = [objects[p] for p in permutation]``
    """
    seen = [False] * len(permutation)
    for i, already_seen in enumerate(seen):
        if not already_seen: # start permutation cycle
            first_obj, j = objects[i], i
            while True:
                seen[j] = True
                p = permutation[j]
                if p == i: # end permutation cycle
                    objects[j] = first_obj    # [old] p -> j
                    break
                objects[j], j = objects[p], p #       p -> j

Алгоритм (как я заметил после того, как я его написал) аналогичен алгоритму @meriton answer в Java.

Здесь функция test для кода:

def test():
    import itertools
    N = 9
    for perm in itertools.permutations(range(N)):
        L = range(N)
        LL = L[:]
        rearrange(L, perm)
        assert L == [LL[i] for i in perm] == list(perm), (L, list(perm), LL)

    # test whether assertions are enabled
    try:
        assert 0
    except AssertionError:
        pass
    else:
        raise RuntimeError("assertions must be enabled for the test")

if __name__ == "__main__":
    test()

Ответ 6

Здесь сортировка гистограммы, хотя время выполнения задано как бит выше O (N) (N log log n).

Ответ 7

Я могу сделать это с помощью O (N) места царапины - скопировать в новый массив и скопировать назад.

EDIT: Я знаю о существовании алгоритма, который будет продолжаться. Идея состоит в том, чтобы выполнить свопы по массиву целых чисел 1..N и в то же время отражать свопы в вашем массиве больших объектов. Я просто не могу найти алгоритм прямо сейчас.

Ответ 8

Проблема заключается в применении перестановки на месте с минимальным O (1) дополнительным хранилищем: "in-situ перестановка".

Он разрешен, но алгоритм не очевиден заранее.

Это кратко описано как упражнение в Кнуте, и для работы мне пришлось расшифровать его и выяснить, как он работает. Посмотрите на 5.2 # 13.

Для более современной работы над этой проблемой с псевдокодом:

http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/forschung/berichte/bericht_273.pdf

Ответ 9

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

void make_swaps(vector<int> order, vector<pair<int,int>> &swaps)
{
    // order[0] is the index in the old list of the new list first value.
    // Invert the mapping: inverse[0] is the index in the new list of the
    // old list first value.
    vector<int> inverse(order.size());
    for(int i = 0; i < order.size(); ++i)
        inverse[order[i]] = i;

    swaps.resize(0);

    for(int idx1 = 0; idx1 < order.size(); ++idx1)
    {
        // Swap list[idx] with list[order[idx]], and record this swap.
        int idx2 = order[idx1];
        if(idx1 == idx2)
            continue;

        swaps.push_back(make_pair(idx1, idx2));

        // list[idx1] is now in the correct place, but whoever wanted the value we moved out
        // of idx2 now needs to look in its new position.
        int idx1_dep = inverse[idx1];
        order[idx1_dep] = idx2;
        inverse[idx2] = idx1_dep;
    }
}

template<typename T>
void run_swaps(T data, const vector<pair<int,int>> &swaps)
{
    for(const auto &s: swaps)
    {
        int src = s.first;
        int dst = s.second;
        swap(data[src], data[dst]);
    }
}

void test()
{
    vector<int> order = { 2, 3, 1, 4, 0 };

    vector<pair<int,int>> swaps;
    make_swaps(order, swaps);

    vector<string> data = { "a", "b", "c", "d", "e" };
    run_swaps(data, swaps);
}