题
假设我有一个 int T 的数组, 我正在寻找一种将 i 和 T[i] 置换的就地算法
我有 :[3 2 0 1](一)
我想 :[2 3 1 0] (b)
例如。(b) 中 T[0] = 2,因为 (a) 中 T[2] 等于 0。
我本来希望找到一个简单的 O(n) 时间、O(1) 空间算法,但我找不到它。有任何想法吗 ?
笔记 :
有一个数组(a)在之前(b)在之后。
数组中的值属于[0,N[,不重复。
解决方案
要获得排列的反转,您只需遍历排列的循环
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 的数字来标记这是已处理的循环的一部分。
其他提示
您可以采用字典顺序来获取所有可能的排列。请点击下面的链接获取排列算法列表
看来你正在寻找逆 排列群 一个数组的。您的示例数组是 {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 ..n-1],tinv 不应为任何值未定义。jpalecek 的解决方案有点复杂,所以我不确定这个解决方案对您来说是否足够全面。
这是我尝试在没有额外内存的情况下就地解决这个问题。这是一个 O(n) 算法。
jpalecek 的算法非常智能,但阅读起来并不直观,至少对我来说不是。我已经尝试过并且有效,但我没有时间理解为什么,评论会很棒。
只要数组不是太大,Gracenotes 的算法就很好。如果数据很大,可能需要动态创建数组。
我的算法的基本思想是通过遵循索引和值对链来更新数组。例如,索引 0 映射到值 3。通过使用值 3 作为索引,您将找到下一对,即数组中的索引 3 和值 1。本质上,我保存下一个索引和值对,并更新前一个索引和值对,直到完成链。
如果你能让它更高效、更优雅或者整体更好,我会很感兴趣。
我已经编译并测试了下面的代码,但没有使用任何其他测试输入。我为那些希望尝试并更好地了解其工作原理的人留下了调试输出。
// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
printf ("%s\n", str_p);
for (int i = 0; i < n; i++)
{
printf ("%i ", i);
}
printf ("\n");
for (int i = 0; i < n; i++)
{
printf ("%i ", a[i]);
}
printf ("\n\n");
}
// The main code.
void PermuteTheDamnArray()
{
printArray ("Initial Array", a,n);
int i = 0; // Simply a counter.
int p_ix = 0; // Previous Index.
int p_val = a[0]; // Previous Value.
int n_ix = a[0]; // Next index.
int n_val = a[n_ix]; // Next Value.
for (i = 0; i < n; i++)
{
// Replace.
printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
a[p_val] = p_ix;
printArray ("Array after swap", a,n);
// The next index and value pair becomes the new previous index and value pair.
p_ix = n_ix;
p_val = n_val;
printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);
// Get the next index and value pair.
n_ix = n_val;
n_val = a[n_val];
printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);
}
printArray ("Final Array", a,n);
}
Output:
Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3
3 2 0 0
The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3
3 3 0 0
The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3
3 3 1 0
The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3
2 3 1 0
The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3
2 3 1 0