Вращение массива с использованием алгоритма Juggling

Недавно я узнал о том, как алгоритм Juggling вращает массив в линейном времени, когда я читал это решение в книге Programming Pearls.

Код для его решения был следующим:

/*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;
  }
}

У меня есть два вопроса относительно этого алгоритма -

  • Как GCD определяет количество циклов, необходимых для поворота массив?
  • Почему, когда мы заканчиваем цикл, мы начинаем новый цикла из следующего элемента, т.е. не может следующий элемент быть уже часть обработанного цикла?

Я чувствую, что мне не хватает чего-то фундаментального в отношении работы GCD, модуля и циклов.

Следующий вопрос был ответом на мой первый вопрос, но все же я не смог его понять.

Жесткий алгоритм поворота строки

Таким образом, было бы полезно, если бы кто-то мог объяснить это в неспециалистских терминах и принцип, по которому они все гель вместе, чтобы заставить этот алгоритм работать.

Ответы

Ответ 1

Как GCD определяет количество циклов, необходимых для вращения массива?

Поскольку внутренний цикл увеличивается с шагом d и останавливается, когда он возвращается к исходной точке, т.е. полный диапазон, который несколько кратно n. Это кратность LCM(n, d). Таким образом, количество элементов в этом цикле LCM(n, d) / d. Общее число таких циклов равно n / (LCM(n, d) / d), что равно GCD(n, d).

Почему так, как только мы заканчиваем цикл, мы запускаем новый цикл из следующего элемента, т.е. не может ли следующий элемент быть частью обработанного цикла?

Нет. Внутренний цикл увеличивается с шагом d, который кратен GCD(n, d). Таким образом, к моменту начала цикла i -th, для хита нам понадобится (k*GCD + z) % n == i (для 0 <= z < i). Это приводит к (k*GCD) % n == (i - z). У этого явно нет решений.

Ответ 2

GCD - действительно пример красоты математики. Иногда, когда вы получаете вещь в своем уме, ваш ум будет отвечать сам за то, что он делает, как это происходит в стороне.

Теперь, задаваясь вопросом, задача вращения просто могла быть обработана с помощью цикла for. Алгоритм Juggling может иметь некоторые преимущества по сравнению с ним (я не нашел что).

Теперь подходит к точке Почему GCD. GCD дает точный график вращения. Это фактически минимизирует количество поворотов.

Например,

если вы хотите выполнить поворот на 30 номеров

с d = 1 внешний контур будет вращаться один раз, а внутренний будет вращаться в 30 раз 1*30=30

с d = 2 внешний контур будет вращаться дважды, а внутренний будет вращаться 15 раз 2*15=30

с d = 3 внешний цикл будет вращаться трижды, а внутренний будет вращаться в 10 раз 3*10=30

Итак, GCD Здесь гарантируется, что вращение не будет превышать значение 30. И поскольку вы получаете число, являющееся делителем общих элементов, оно не позволит пропустить любой элемент