3

假设我有一个 int T 数组，我正在寻找一种置换 i 和 T[i] 的就地算法

我有：[3 2 0 1] (a)

我想要：[2 3 1 0] (b)

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

我期待找到一个简单的 O(n) 时间、O(1) 空间算法，但我找不到。有任何想法吗 ？

笔记 ：

  • 有一个单一的数组（a）在之前（b）在之后。

  • 数组中的值属于 [0, N[, 没有重复。

4

4 回答 4

4

要获得排列的反转，您只需要遍历排列的循环

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 的数字来标记这是已处理的循环的一部分。

于 2009-03-02T09:26:35.337 回答
1

您可以进行字典排序以获得所有可能的排列。按照下面的链接获取置换算法列表

排列

于 2009-03-02T09:27:07.537 回答
1

您似乎正在寻找数组的排列组中的逆。您的示例数组是 {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 的解决方案稍微复杂一些，所以我不确定这个解决方案是否对您来说足够全面。

于 2009-03-02T10:06:37.207 回答
0

这是我在没有额外内存的情况下就地解决这个问题的尝试。这是一个 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
于 2009-03-07T03:01:15.690 回答