Яблочная клавиатура Apple на Precise

Я нашел статью, которая пытается объяснить это здесь: Почему алгоритм Хипа работает?

Однако, я думаю, что это трудно понять, поэтому придумал объяснение, которое, мы надеемся, будет легче понять:

Пожалуйста, просто предположите, что эти утверждения верны на мгновение (я покажу это позже):

Каждый вызов " генерировать "функцию

(I), где n нечетно, оставляет элементы в том же порядке, когда они закончены.

(II), где n четно, вращает элементы в справа, например, ABCD становится DABC.

Итак, в «для i» -loop

, когда

• n четно Рекурсивный вызов " generate (n - 1, A) "не изменяет порядок. Таким образом, for-loop может итеративно поменять элемент на i = 0 .. (n-1) с элементом at (n - 1) и будет каждый раз вызывать «generate (n - 1, A)» с отсутствием другого элемента .
• n нечетно. Рекурсивный вызов «generate (n - 1, A)» повернул элементы вправо. Таким образом, элемент с индексом 0 всегда будет другим элементом автоматически. Просто замените элементы на 0 и (n-1) на каждой итерации, чтобы создать уникальный набор элементов.

Наконец, давайте посмотрим, почему исходные утверждения верны:

Поворот справа

(III) Эта серия свопов приводит к повороту вправо на одну позицию:

A[0] <-> A[n - 1]
A[1] <-> A[n - 1]
A[2] <-> A[n - 1]
...
A[n - 2] <-> A[n - 1]

Например, попробуйте с последовательностью ABCD :

A[0] <-> A[3]: DBCA
A[1] <-> A[3]: DACB
A[2] <-> A[3]: DABC

No-op

(IV) Эта серия шагов оставляет последовательность в том же порядке, что и раньше:

Repeat n times:
    Rotate the sub-sequence a[0...(n-2)] to the right
    Swap: a[0] <-> a[n - 1]

Интуитивно , это правда:

Если у вас есть последовательность длины 5, затем поверните ее 5 раз, она не изменится.

Принимая элемент в 0 перед вращением, тогда после поворота, заменяющего его новым элементом на 0, не изменяет результат (если он вращается n раз).

Индукция

Теперь мы можем видеть, почему (I) и (II) истинны:

Если n равно 1: Тривиально, после вызова функции порядок не изменяется.

Если n равно 2: рекурсивные вызовы «сгенерируют (n - 1, A) «оставьте заказ ng без изменений (потому что он вызывает генерировать с первым аргументом, равным 1). Поэтому мы можем просто игнорировать эти призывы.

Если n равно 3: рекурсивные вызовы «generate (n - 1, A)» приводят к правому вращению, см. (III).

вращение. Таким образом, полные этапы этого вызова равны (IV) => Последовательность не изменяется.

Повторите для n = 4, 5, 6, ...