permute I和T[i]

Question

假设我有一个int T数组，我正在寻找一种使i和Ti保持不变的就地算法。

我有：3 2 0 1

我要：2 3 1 0

例如：在(b) T=2中，因为在(a)中，T2等于0。

我本来希望找到一个简单的O(n)时间，O(1)空间算法，但我找不到。有什么想法吗？

注意：

• 在(b)之后有一个单元组(a)。
• 数组中的值属于[0，N[，不重复“)。

Answer 1

要得到置换的反转，只需遍历置换的循环即可。

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

我使用大于N的数字来标记，这是已经处理过的循环的一部分。

Answer 2

你可以去字典排序，得到所有可能的排列。按照下面的链接获得排列算法的列表。

排列

Answer 3

似乎您在寻找数组的置换群中的逆值。示例数组是{0→3，1→2，2→0，3→1}，您需要{3→0，2→1，0→2，1→3}。重新排列，即{ 0→2，1→3，2→1，3→0}，或2 3 1 0。因此，要找到逆值，只需遍历原始数组并反转索引的映射。这应该有效(如果知道长度，可以使用任意数组)：

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

只要t(长度n)是0的置换。对于任何值，tinv都不应该没有定义。jpalecek的解决方案有点复杂，所以我不确定这个解决方案是否足够全面。