python - 具有排列签名的堆算法

Question

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

一般来说，排列数由第一类斯特林数给出，作为划分 n 个元素的 k = 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) 返回第 l 直到 的每个排列r-a 的第一个字母 and 退出，a 等于执行开始时的值。

通过r - l 归纳可以直接证明这一点。如果没有声明中“退出时 a 相等”部分，那就很难了。

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

Knuth 的 TAoCP(第 4A 卷)第 7.2.1.2 节致力于生成所有排列的算法。其中一些也可以轻松修改以生成其标志。我想知道你的是否也在其中。