带置换签名的堆算法
带置换签名的堆算法
提问于 2019-02-04 23:27:29
我正在做一个代码，可以生成元素列表的所有排列和基于原始列表的置换签名。
一般情况下，排列数是由第一类Stirling数作为k=n环的组合来划分n个元素。
[n] [n - 1] [n - 1]
[ ] = (n - 1) [ ] + [ ]
[k] [ k ] [k - 1]将n个元素划分为k个循环的方法是将n-1非最大元素划分为k个循环，并在n-1方式之一的最大元素中拼接，或将最大元素放在它自己的循环中，并将n-1非最大元素划分为k-1循环。然后，符号将由(-1)^N给出，其中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的第一个成员是在本例中为+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
Stack Overflow用户
回答已采纳
发布于 2019-02-08 03:16:07
是的，你的方法是正确的。与其直接证明这一点，不如证明
(1) (1) permute(a, l, r)的执行将返回l-th的每个置换，直到和完全退出r-th a字母为止，a等于执行开始时的值。
通过在r - l上的归纳可以直观地证明这一点。如果没有声明中的“a相等的退出”部分，就很难做到。
至于符号是正确的，这只是一个循环不变式:每次你交换两个不同的条目，你把符号乘以-1，这是你唯一改变符号的时间。因此，是的，第0项是在您的过程中的每一次排列的标志。
Knuth的TAoCP (第4A卷)的第7.2.1.2节专门讨论生成所有排列的算法。它们中的一些也可以很容易地被修改以产生它们的标志。我想知道你是否也在其中。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54525821
复制相关文章
相似问题
腾讯云开发者
