具有置换签名的堆算法

Question

我正在制作一个代码，可以生成元素列表的所有排列以及基于原始列表的排列签名。

一般来说，排列的数量由第一类斯特林数给出，作为 k = n - 划分 n 个元素的 C 循环的组合。

       [n]           [n - 1]   [n - 1]
       [ ] = (n - 1) [     ] + [     ]
       [k]           [  k  ]   [k - 1]

将n个元素划分成k个循环的方法是将n - 1个非最大元素划分成k个循环，然后将最大元素按n - 1种方法之一拼接或将最大元素单独放入将n-1个非极大值元素循环划分为k-1个循环。然后，符号将由 (-1)^N-C 给出，其中 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]？有没有更有效的方法来生成排列及其符号？

Answer 1

是的，你的方法是正确的。与其直接证明这一点，不如证明

(1) permute(a, l, r) returns 的每个排列的执行 l-th 直到 r-th a 的字母恰好一次和以 a 等于执行开始时的值退出。

这可以通过 r - l 上的归纳法直接证明。如果没有索赔的 "exits with a being equal" 部分，那就很难了。

至于符号是否正确，这只是一个循环不变量：每次交换两个不同的条目时，您都会将符号乘以 -1，这是唯一一次更改符号。所以是的，第 0 个条目是您过程中每次排列的符号。

Knuth 的 TAoCP（第 4A 卷）的第 7.2.1.2 节专门介绍生成所有排列的算法。其中一些也可以很容易地修改以生成它们的标志。我想知道你的是否在其中。

具有置换签名的堆算法

Heap's algorithm with permutation signature

python

permutation

combinatorics

parity

heaps-algorithm