使用 Juggling 算法旋转数组 [英] Rotating an array using Juggling algorithm

问题描述

我最近在阅读 Programming Pearls 一书中的解决方案时了解了 Juggling 算法 如何在线性时间内旋转数组.

I recently learnt about how the Juggling algorithm rotates an array in linear time when I was reading the solution in the Programming Pearls book.

解决它的代码如下:

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  for (i = 0; i < gcd(d, n); i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

关于这个算法我有两个问题 -

I have two questions regarding this algorithm -

1. GCD 如何决定旋转所需的周期数数组?
2. 为什么一旦我们完成一个循环，我们就开始新的从下一个元素开始循环，即.下一个元素不能已经是一个处理周期的一部分?

我觉得，关于GCD、模数和循环的工作，我缺少一些基本的东西.

I feel, I am missing something fundamental regarding the working of GCD, modulus and the cycles.

下面的问题已经回答了我的第一个问题，但我仍然无法理解.

The following question had an answer to my first question, but still I was not able to understand it.

字符串旋转的杂耍算法

因此，如果有人能通俗易懂地解释它以及它们如何结合在一起使该算法起作用的原理，那将会很有帮助.

So, it would be helpful if someone can explain it in layman terms and the principle behind how they all gel together to make this algorithm work.

推荐答案

GCD 如何决定旋转阵列所需的周期数?

How does the GCD decide the number of cycles needed to rotate the array?

因为内循环以 d 的步长递增，并在返回起点时停止，即总跨度是 n 的倍数.该倍数是 LCM(n, d).因此，该循环中的元素数量是LCM(n, d)/d.这样的循环总数为n/(LCM(n, d)/d)，等于GCD(n, d).

Because the inner loop increments in steps of d, and stops when it gets back to the starting point, i.e. a total span which is some multiple of n. That multiple is LCM(n, d). Thus the number of elements in that cycle is LCM(n, d) / d. The total number of such cycles is n / (LCM(n, d) / d), which is equal to GCD(n, d).

为什么一旦我们完成一个循环，我们就从下一个元素开始新的循环，即下一个元素不能已经是已处理循环的一部分?

Why is it that once we finish a cycle, we start the new cycle from the next element i.e. can't the next element be already a part of a processed cycle?

没有.内循环以d的步长递增，它是GCD(n, d)的倍数.因此，当我们开始第 i 个循环时，对于一次命中，我们需要 (k*GCD + z) % n == i(对于 0 <= z ).这导致 (k*GCD) % n == (i - z).这显然没有解决方案.

No. The inner loop increments in steps of d, which is a multiple of GCD(n, d). Thus by the time we start the i-th cycle, for a hit we'd need (k*GCD + z) % n == i (for 0 <= z < i). This leads to (k*GCD) % n == (i - z). This clearly has no solutions.

这篇关于使用 Juggling 算法旋转数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！