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

问题描述

我最近学会了如何在戏法算法旋转线性时间序列，当我读了编程珠玑书的解决方案。

的code，以解决这个问题如下：

  / *功能，以左侧为d *旋转[] SIZ为n的ARR /
无效leftRotate（INT改编[]，INT研发，INT N）
{
  INT I，J，K，温度;
  对于（i = 0; I＆LT; GCD（D，N）;我++）
  {
    / *块移动的第i个值* /
    TEMP = ARR [I]
    J =;
    而（1）
    {
      K = J + D组;
      如果（K＆GT; = N）
        k = k  -  N;
      如果（K == I）
        打破;
      ARR [J] = ARR [K]
      J = K表;
    }
    ARR [J] =温度;
  }
}
 

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

1. 如何GCD的决定以旋转所需要的周期数 阵列？
2. 为什么一旦我们完成一个周期，我们开始了新的 周期从下一个元件即。不能下一个元素是一个已经 一个加工周期的一部分？

我觉得，我是缺少关于工作的东西根本的 GCD 系数和周期。

下面的问题有一个答案，我的第一个问题，但我仍然无法理解这一点。

杂耍柱旋转算法

所以，这将是有益的，如果有人能在浅白后面怎么都凝胶在一起，使这种算法的工作原理解释。

感谢

P.S。 - 这是我的第一个问题在这里，所以请随时告诉我，如果我需要提供更多的信息，或者我需要改变我的问题的格式

解决方案

  

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

由于在步骤 D 的内循环递增，而当它得到返回到起点停止时，即总跨度是的某个倍数<$ C $ ç> N 。这多是 LCM（N，D）。因此，在该周期的元素的数目是 LCM（N，D）/ d的。这种循环的总数为 N /（LCM（N，D）/ D），这等于 GCD（N，D）。

  

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

没有。在步骤 D ，这是 GCD的倍数的内环增量（N，D）。这样的时候，我们开始了我周期中，一击，我们就需要（K * GCD + Z）％N ==我（对于 0℃= z，其中;我）。这导致了（K * GCD）％N ==（I - Z）。这显然​​没有解决方案。

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.

The code to solve it was as follows:

/*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. How does the GCD decide the number of cycles needed to rotate the array?
2. Why is it that once we finish a cycle, we start the new cycle from the next element ie. can't the next element be already a part of a processed cycle?

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.

Juggling algorithm of string rotation

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.

Thanks

P.S. - This is my first question here, so please feel free to tell me if I need to provide more information or I need to change the format of my question.

解决方案

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

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?

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.

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