Объяснение алгоритма перестановки кучи [duplicate]

Алгоритм Кучи, вероятно, не является ответом на какой-либо разумный вопрос интервью. Существует гораздо более интуитивный алгоритм, который будет производить перестановки в лексикографическом порядке; хотя он амортизируется O (1) (за перестановку) вместо O (1), на практике он не заметно медленнее, и его намного легче вывести на лету.

Алгоритм лексикографического порядка чрезвычайно просто описать. Для некоторой перестановки найдите следующую:

1. Поиск самого правого элемента, который меньше, чем элемент справа.
2. Смените этот элемент с наименьшим элементом на его
3. Переверните часть перестановки справа от того, где был этот элемент.

Оба этапа (1) и (3) являются в худшем случае O (n), но нетрудно доказать, что среднее время для этих шагов равно O (1).

Индикация того, как сложный алгоритм Кучи (в деталях) заключается в том, что ваше выражение это немного неправильно, потому что он делает один дополнительный обмен; дополнительный swap - это no-op, если n четный, но создает проблему, когда n нечетно. См. https://en.wikipedia.org/wiki/Heap%27s_algorithm для правильного алгоритма (по крайней мере, это правильно сегодня) или см. Обсуждение в Генератор перестановок алгоритма Heap's

Чтобы увидеть, как работает алгоритм Хипа, вам нужно посмотреть, что представляет собой полная итерация цикла для вектора, как в четном, так и в нечетном случае. Для вектора четной длины полная итерация алгоритма Куба оставит вектор повернутым влево на одну позицию. Если вектор имеет нечетную длину, то в конце алгоритма вектор будет обратным. Вы можете доказать, что оба эти факта верны с использованием индукции, хотя это не дает никакой интуиции относительно того, почему это правда. Глядя на диаграмму на странице Википедии, может помочь.

Причина, по которой алгоритм Куба строит все перестановки, состоит в том, что он присоединяет каждый элемент к каждой перестановке остальных элементов. Когда вы выполняете алгоритм кучи, рекурсивные вызовы на входы с длинной длиной помещают элементы n, (n-1), 2, 3, 4, ..., (n-2), 1 в последнюю позицию, а рекурсивные вызовы на входах с нечетной длиной помещают элементы n, (n-3), (n-4), (n-5), ..., 2, (n-2), (n-1), 1 в последнюю позицию. Таким образом, в любом случае все элементы связаны со всеми перестановками элементов n - 1.

Если вы хотите более подробное графическое объяснение, посмотрите эту статью .

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

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

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

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

(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, ...

Я знаю, что этот вопрос требует языкового агностика, но Ruby во многих случаях читает лучше, чем псевдокод, и его легче запоминать, потому что он очень компактен:

def gen_perms (list, n=list.size - 1 )

  return p list if n.zero? 

  for i in 0..n do
    gen_perms list, n - 1
    list[1], list[n] = list[n], list[1] if n.even?
    list[i], list[n] = list[n], list[i] if n.odd?
  end
end

list = ['a','b','c']

gen_perms list