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

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

// 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's 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
        }
    }

Вы имеете в виду, что у вас есть массив объектов 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 [].

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

РЕДАКТИРОВАТЬ: Другие уже представили отличные решения, пока я спал, так что не нужно повторять это здесь. ^ _ ^

РЕДАКТИРОВАТЬ: Мое дополнительное пространство O (1) действительно не совсем правильно. Я думал только об элементах «данных», но на самом деле вам также нужно хранить один бит на элемент перестановки, поэтому, если мы точны, нам нужно O (log n) дополнительных битов для этого. Но в большинстве случаев использование знакового бита (как было предложено Дж. Ф. Себастьяном) нормально, поэтому на практике нам может не понадобиться ничего больше, чем мы уже имеем.

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

#!/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). Это было бы немного сложнее и заняло бы немного больше места, так что это та версия, которую я написал, но модификации не должны быть трудными.

РЕДАКТИРОВАТЬ: На самом деле, я почти уверен, что временная сложность просто O (n), поскольку с каждым порядком может быть связано не более одного интервала, и, таким образом, максимальное количество поисков ограничено n.

#!/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 на 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()

There's a histogram sort, though the running time is given as a bit higher than O(N) (N log log n).

I can do it given O(N) scratch space -- copy to new array and copy back.

EDIT: I am aware of the existance of an algorithm that will proceed through. The idea is to perform the swaps on the array of integers 1..N while at the same time mirroring the swaps on your array of large objects. I just cannot find the algorithm right now.

Проблема заключается в применении перестановки на месте с минимальным объемом памяти O (1): «перестановка на месте».

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

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

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

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