我看到这个问题是一个编程采访的书，我在这里简化了问题。
假设你有一个数组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)空间）。
想法？
Answer 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）的平凡。
Answer 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)
谢谢！
Answer 3:
只是一个简单的例子，C / C ++代码除了Ziyao伟的答案。 代码是不允许在评论，这样的回答，抱歉：
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 ::交换别的东西）
Answer 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)
该算法，虽然不是最快的，避免了额外的内存分配，同时仍然保持元素的初始秩序的轨道。
Answer 5:
这里更清晰的版本，这需要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];
}
}
Answer 6:
@RinRisson 已经给了我们唯一完全正确的答案为止！ 每隔答案一直的东西，需要额外的存储空间 - O（n）的堆栈空间，或者假设置P被方便地存储毗邻O（n）的未使用的，但是，可变标志位，或什么的。
这里的RinRisson在C ++编写出正确的答案。 这通过每个测试我已经在它抛出，包括通过11长度为0的每个可能的排列的穷尽测试。
请注意，你甚至不需要被物化排列; 我们可以把它当作一个完全的黑盒函数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); });
}
Answer 7:
我有很多的解决方案达成一致这里，但低于在整个置换周期中置换一个很短的代码片段：
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]
文章来源: Algorithm to apply permutation in constant memory space
