Алгоритм кучи с перестановкой подписи
Я делаю код, который может генерировать все перестановки списка элементов и подписи перестановки на основе исходного списка.
В общем случае число перестановок задается числами Стирлинга первого рода как композиция из k = n - C-циклов, которые разбивают n элементов.
[n] [n - 1] [n - 1]
[ ] = (n - 1) [ ] + [ ]
[k] [ k ] [k - 1]
Количество способов разбить n элементов на k циклов состоит в том, чтобы разделить n - 1 не максимальный элемент на k циклов и объединить максимальный элемент одним из n - 1 способов или поместить максимальный элемент в его собственный цикл и разбить n - 1 не максимальный элемент в k - 1 цикл. Тогда знак будет задан формулой (-1)^NC, где N - количество индексов, а C - количество циклов, образованных при перемещении элемента из исходного положения.
Я кодировал вариант алгоритма кучи, который может производить сигнатуру каждой перестановки.
def permute(a, l, r):
if l==r:
print'Permutation--:',a
else:
for i in xrange(l,r+1):
if i!=l:
a[0]=(-1)*int(a[0])#Sign for permutation
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l]
if i!=l:#Sign for permutation
a[0]=(-1)*int(a[0])
test = "1hgfe"
n = len(test)
a = list(test)
permute(a, 1, n-1)
В процедуру перестановки списка a вводится первый член списка, a[0] - это знак, который в этом случае равен +1, и для каждой перестановки пение списка умножается на -1. Пока я думаю, что код работает, это результат теста.
['1', 'h', 'g', 'f', 'e'] (h->h) (g->g) (f->f) (e->e) (-1)^(4-4) or identity =+1
[-1, 'h', 'g', 'e', 'f'] (h->h) (g->g) (f->e) (-1)^(4-3)=-1
[-1, 'h', 'f', 'g', 'e'] (h->h) (g->f) (e->e) (-1)^(4-3)=-1
[1, 'h', 'f', 'e', 'g'] (h->h) (g->f->e) (-1)^(4-2)=+1
[-1, 'h', 'e', 'f', 'g'] (h->h) (g->e) (f->f) (-1)^(4-3)=-1
[1, 'h', 'e', 'g', 'f'] (h->h) (g->e->f) (-1)^(4-2)=+1
[-1, 'g', 'h', 'f', 'e'] (h->g) (f->f) (e->e) (-1)^(4-3)=-1
[1, 'g', 'h', 'e', 'f'] (h->g) (f->e) (-1)^(4-2)=+1
[1, 'g', 'f', 'h', 'e'] (h->g->f) (e->e) (-1)^(4-2)=+1
[-1, 'g', 'f', 'e', 'h'] (h->g->f->e) (-1)^(4-1)=-1
[1, 'g', 'e', 'f', 'h'] (h->g->e) (f->f) (-1)^(4-2)=+1
[-1, 'g', 'e', 'h', 'f'] (h->g->e->f) (-1)^(4-1)=-1
[-1, 'f', 'g', 'h', 'e'] (h->f) (g->g)(e->e) (-1)^(4-3)=-1
[1, 'f', 'g', 'e', 'h'] (h->f->e) (g->g) (-1)^(4-2)=+1
[1, 'f', 'h', 'g', 'e'] (h->f->g) (e->e) (-1)^(4-2)=+1
[-1, 'f', 'h', 'e', 'g'] (h->f->e->g) (-1)^(4-1)=-1
[1, 'f', 'e', 'h', 'g'] (h->f) (g->e) (-1)^(4-2)=+1
[-1, 'f', 'e', 'g', 'h'] (h->f->g->e) (-1)^(4-1)=-1
[-1, 'e', 'g', 'f', 'h'] (h->e) (g->g) (f->f) (-1)^(4-3)=-1
[1, 'e', 'g', 'h', 'f'] (h->e->f) (g->g) (-1)^(4-2)=+1
[1, 'e', 'f', 'g', 'h'] (h->e) (g->f) (-1)^(4-2)=+1
[-1, 'e', 'f', 'h', 'g'] (h->e->g->f) (-1)^(4-1)=-1
[1, 'e', 'h', 'f', 'g'] (h->e->g) (f->f) (-1)^(4-2)=+1
[-1, 'e', 'h', 'g', 'f'] (h->e->f->g) (-1)^(4-1)=-1
Мои вопросы: Как вы думаете, мой код будет применим к любому размеру списка, то есть [1,A,B,C......,Z_n]? Есть ли более эффективный способ генерировать перестановки и их знаки?
1 ответ
Да, ваш метод правильный. Вместо того, чтобы доказать это прямо, вы должны доказать, что
(1) выполнение permute(a, l, r) возвращает каждую перестановку lдо rбуквы a ровно один раз и выходит с a быть равным тому, что было в начале казни.
Это легко доказать по индукции на r - l, Без "выходов с a быть равным "части претензии, было бы сложно.
Что касается правильных знаков, то это просто инвариант цикла: каждый раз, когда вы меняете две разные записи, вы умножаете знак на -1, и это единственный раз, когда вы меняете знак. Так что да, 0-я запись - это знак перестановки в каждый момент вашего процесса.
TAoCP Кнута (том 4А) имеет раздел 7.2.1.2, посвященный алгоритмам, генерирующим все перестановки. Некоторые из них также могут быть легко изменены, чтобы генерировать свои знаки. Мне интересно, если ваш среди них.