就地arrays重新sorting？
比方说，我有一个长度为n的数组，另外还有一个长度为n数组。 indices包含序列[0, n)任意排列。 我想重新排列a这样的indices指定的顺序。 例如，使用D语法：
auto a = [8, 6, 7, 5, 3, 0, 9]; auto indices = [3, 6, 2, 4, 0, 1, 5]; reindexInPlace(a, indices); assert(a == [5, 9, 7, 3, 8, 6, 0]);
这可以在O（1）空间和O（n）时间内完成，最好不要改变indices ？
随着变异indices :(。不看起来很难（见稳定的就地mergesort）。
a = [8, 6, 7, 5, 3, 0, 9] indices = [3, 6, 2, 4, 0, 1, 5] for i in xrange(len(a)): x = a[i] j = i while True: k = indices[j] indices[j] = j if k == i: break a[j] = a[k] j = k a[j] = x print a
这就是我所说的“从algorithm排列”。 在C语言中，它看起来如下
for (i_dst_first = 0; i_dst_first < n; ++i_dst_first) { /* Check if this element needs to be permuted */ i_src = indices[i_dst_first]; assert(i_src < n); if (i_src == i_dst_first) /* This element is already in place */ continue; i_dst = i_dst_first; pending = a[i_dst]; /* Follow the permutation cycle */ do { a[i_dst] = a[i_src]; indices[i_dst] = i_dst; i_dst = i_src; i_src = indices[i_src]; assert(i_src != i_dst); } while (i_src != i_dst_first); a[i_dst] = pending; indices[i_dst] = i_dst; }
注意这个algorithm破坏了index数组。 我把它称为“permute from”，因为index[i]值指定了从哪里获取结果序列的第i个元素。
还需要注意的是，序列就地置换所需的“元素移动”操作的number of misplaced elements等于置换number of misplaced elements number of cycles in the permutation + number of cycles in the permutation 。 这个algorithm达到了这个限制，所以就移动次数而言，没有更好的algorithm是可能的。
这个algorithm的潜在问题是它是基于“杂耍”的方法，使得它的caching行为远不是最优的。 所以，虽然这个algorithm在理论上是最好的，但在现实生活中可能会丢失一些更“实用”的algorithm。
也可以实现“permute to”algorithm，其中index[i]值指定将原始第i个元素重定位到何处。
如果a是一个整数数组，那么一个O（n）时间O（1）空间algorithm是可能的，它保持排列indices的顺序。 在这种情况下，我们可以将a排列成indexes并使用a作为逆置换的临时存储。 在置换之后，交换arraysa和indices ，并且使用例如来自TAoCP的algorithmJ原位反转indices 。 以下是一个正在运行的Java程序：
int [] a = {8, 6, 7, 5, 3, 0, 9}; int [] indices = {3, 6, 2, 4, 0, 1, 5}; int n = indices.length; int i, j, m; // permute a and store in indices // store inverse permutation in a for (j = 0; j < n; ++j) { i = indices[j]; indices[j] = a[i]; a[i] = j; } // swap a and indices for (j = 0; j < n; ++j) { i = indices[j]; indices[j] = a[j]; a[j] = i; } // inverse indices permutation to get the original for (i = 0; i < n; ++i) {indices[i] = -indices[i] - 1;} for (m = n - 1; m >= 0; --m) { // for (i = m, j = indices[m]; j >= 0; i = j, j = indices[j]) ; i = m; j = indices[m]; while (j >= 0) {i = j; j = indices[j];} indices[i] = indices[-j - 1]; indices[-j - 1] = m; }
这回答indices数组是可变的问题。
这是一个not变的解决scheme。
void mutate(int[] input, int[] indices) { int srcInd; for (int tarInd = 0; tarInd < input.length; tarInd++) { srcInd = indices[tarInd]; while(srcInd < tarInd) { // when src is behind, it will have it's final value already and the original // value would have been swapped with src's src pos. Keep searching for the // original value until it is somewhere ahead of tarInd. srcInd = indices[srcInd]; } swap(input, srcInd, tarInd); } }
我认为处理这个问题的经典方法是循环工作，为此，每个数据项需要一个标记位。 在这里，我捏了索引数组的最高位，你可以恢复 – 当然这假定你没有-ve数组索引，或者使用一个无符号数的所有位作为索引。 对此的一个参考是Knuth第1卷第1.3.3节对问题12的回答，该问题涉及转置matrix的特殊情况。 Knuth给出了较慢就地方法的参考。 Fich，Munro和Poblete的文章“Permuting in Place”在最坏的情况下声称nlogn时间和O（1）空间。
import java.util.Arrays; public class ApplyPerm { public static void reindexInPlace(int[] rearrangeThis, int[] indices) { final int TOP_BIT = 0x80000000; for (int pos = 0; pos < rearrangeThis.length; pos++) { if ((indices[pos] & TOP_BIT) != 0) { // already dealt with this continue; } if (indices[pos] == pos) { // already in place continue; } // Now shift an entire cycle along int firstValue = rearrangeThis[pos]; int currentLocation = pos; for (;;) { // pick up untouched value from here int replaceBy = indices[currentLocation]; // mark as dealt with for the next time we see it indices[currentLocation] |= TOP_BIT; if (replaceBy == pos) { // have worked our way round rearrangeThis[currentLocation] = firstValue; break; } if ((replaceBy & TOP_BIT) != 0) { throw new IllegalArgumentException("Duff permutation"); } // Move value up rearrangeThis[currentLocation] = rearrangeThis[replaceBy]; // and fill in source of value you have just moved over currentLocation = replaceBy; } } } public static void main(String[] s) { int[] a = new int[] {8, 6, 7, 5, 3, 0, 9}; int[] indices = new int[] {3, 6, 2, 4, 0, 1, 5}; reindexInPlace(a, indices); System.out.println("Result is " + Arrays.toString(a)); } }
你可以通过隐藏真实数组中的值来做到这一点。 通过这种方式，你可以在O（1）空间和O（n）时间都做到这一点。
基本上，您首先遍历索引数组，将指数数组的值存储在正确的位置。 现在可以在你select的algorithm中完成。 对于我来说，我只是简单地把最高有效位位置的数字结尾位存储起来。 在一个遍历中做到这一点。 现在基数组会搞砸了。
在第二次遍历时，将所有的上半部分存储到下半部分。
这种技术的明显缺点是所存储的整数值可以保持多达一半的位数。 意思是如果你正在处理4个字节的整数，值只能是2个字节。 然而，如下代码所示，不是使用数组的一半，而是通过在索引数组中隐藏值，使用更好的algorithm来增强它。 在这里，你将要求在最坏情况下保留的最大位数将是数组的长度，而不是前一种情况下的常数16。 当长度超过2次方时，它会比前者performance得差。
import java.util.Arrays; class MyClass { public static void main(String[] args) { MyClass myClass = new MyClass(); int[] orig_array = {8, 6, 7, 5, 3, 0, 9}; int[] indices = {3, 6, 2, 4, 0, 1, 5}; myClass.meth(orig_array, indices); } public void meth(int[] orig_array, int[] indices){ for(int i=0;i<orig_array.length;i++) orig_array[i] += orig_array[indices[i]] + orig_array[indices[i]] << 15 ; for(int i=0;i<orig_array.length;i++) orig_array[i] = orig_array[i] >> 16; System.out.print(Arrays.toString(orig_array)); } }
这是一个C ++版本（它修改了索引）：
#include <algorithm> #include <iterator> template<class It, class ItIndices> void permutate_from( It const begin, typename std::iterator_traits<It>::difference_type n, ItIndices indices) { using std::swap; using std::iter_swap; for (typename std::iterator_traits<It>::difference_type i = 0; i != n; ++i) { for (typename std::iterator_traits<ItIndices>::value_type j = i; ; ) { swap(j, indices[j]); if (j == i) { break; } iter_swap(begin + j, begin + indices[j]); } } }
例：
int main() { int items[] = { 2, 0, 1, 3 }; int indices[] = { 1, 2, 0, 3 }; permutate_from(items, 4, indices); // Now items[] == { 0, 1, 2, 3 } }
JavaScript版本
var input = [1,2,3,4,5], specArr = [0,2,1,4,3]; function mutate(input, specArr) { var visited = [0,2] for(var i=0; i<specArr.length; i++) { var tmp; //keep track of array items we've already looped through (wouldn't want to mutate twice :D) visited.push(specArr[i]); // if index hasn't changed we do nothing to input arr if (visited.indexOf(1) < 0) { // if it has changed temporarily store the value tmp = input[i]; //swap input array item with spec item input[i] = input[specArr[i]]; //swap specced array item with input item above input[specArr[i]] = tmp; } } } mutate(input, specArr);
