Алгоритм применения перестановки в постоянном пространстве памяти
Я видел, что этот вопрос является книгой интервью по программированию, здесь я упрощаю вопрос.
Предположим, у вас есть массив A длины nи у вас есть массив перестановок P длины n также. Ваш метод вернет массив, где элементы A появится в порядке с индексами, указанными в P,
Быстрый пример: ваш метод требует A = [a, b, c, d, e] а также P = [4, 3, 2, 0, 1], тогда он вернется [e, d, c, a, b], Вам разрешено использовать только постоянное пространство (то есть вы не можете выделить другой массив, который занимает O(n) пространство).
Идеи?
10 ответов
Существует тривиальный алгоритм 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) тривиально.
Еще один ненужный ответ! Этот сохраняет массив перестановок 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),
Спасибо!
@RinRisson дал пока единственный правильный ответ! Каждый другой ответ был чем-то, что требовало дополнительной памяти - O(n) стекового пространства или предполагалось, что перестановка P была удобно сохранена рядом с O(n) неиспользованными, но изменяемыми знаковыми битами, или чем-то еще.
Вот правильный ответ РинРиссона, написанный на 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); });
}
Самый простой случай - это когда есть только один обмен для элемента в целевом индексе. например: array =abcdperm =1032. вам просто нужно два прямых обмена: ab swap, cd swap
в других случаях нам нужно продолжать менять местами, пока элемент не достигнет своего конечного пункта назначения. например: abcd, 3021, начиная с первого элемента, мы меняем местами a и d. мы проверяем, является ли пункт назначения 0 в perm [perm [0]]. это не так, поэтому мы меняем местами a на elem в массиве [perm [perm [0]]], который равен b. снова мы проверяем, достигли ли a места назначения в perm [perm [perm [0]]], и да, это так. так что мы останавливаемся.
мы повторяем это для каждого индекса массива. Каждый элемент перемещается на место только один раз, так что это O(N) с O(1) хранилищем.
def permute(array, perm):
for i in range(len(array)):
elem, p = array[i], perm[i]
while( p != i ):
elem, array[p] = array[p], elem
elem = array[p]
p = perm[p]
return array
Просто простой пример добавления кода C/C++ к ответу Ziyao Wei. Код не допускается в комментариях, поэтому в качестве ответа извините
for (int i = 0; i < count;)
{
// 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;
}
destinations[currentPosition] = -1 - destinations[currentPosition];
}
for (int i = 0; i < count; ++i)
destinations[i] = -1 - destinations[i];
(для C - замените std::swap чем-то другим)
Возвращаемое значение для примера, приведенного в исходном вопросе, неверно.
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])
Здесь более четкая версия, которая принимает функцию 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];
}
}
Следовательно, вы можете поместить желаемый элемент в начало массива, одновременно работая с оставшимся массивом размера (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)
Алгоритм, хотя и не самый быстрый, избегает дополнительного выделения памяти, сохраняя при этом отслеживание начального порядка элементов.
Отследите, что мы поменяли местами, проверив index.
Java, O(N) свопов, O(1) пространство:
static void swap(char[] arr, int x, int y) {
char tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
}
public static void main(String[] args) {
int[] intArray = new int[]{4,2,3,0,1};
char[] charArray = new char[]{'A','B','C','D','E'};
for(int i=0; i<intArray.length; i++) {
int index_to_swap = intArray[i];
// Check index if it has already been swapped before
while (index_to_swap < i) {
// trace back the index
index_to_swap = intArray[index_to_swap];
}
swap(charArray, index_to_swap, i);
}
}
Я согласен со многими решениями здесь, но ниже приведен очень короткий фрагмент кода, который переставляется на протяжении всего цикла перестановок:
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]