Heap's algorithm with permutation signature

Question

I am making a code that can generate all the permutation of a list of elements and the signature of the permutation based on the original list.

In general the number of permutations is given by the Stirling numbers of the first kind as a composition of k = n - C-cycles that partition the n elements.

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

The number of ways to partition n elements into k cycles is to partition n - 1 non-maximum element into k cycles and splice in the maximum element in one of n - 1 way or put the maximum element in its own cycle and partition the n - 1 non-maximum element into k - 1 cycles. Then, the sign will be given by (-1)^N-C where N is the number of indexes and C is the number of cycles formed when an element is moved from their original position.

I have coded a variation of the Heap's algorithm which can produce the signature of each permutation.

    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)

In the routine permute the list a is introduced the first member of the list a[0] is the sign which in this case is +1 and for each permutation, the sing of the list is multiply by -1. So far I think the code works, this is the result for the test.

          ['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

My questions are: Do you think my code will be applicable to any list size, i.e. [1,A,B,C......,Z_n]? Is there a more efficient way to generate the permutations and their signs?

You can use the itertools library. There is a method called permutations. — Igor Dragushhak
– Igor Dragushhak, Commented Feb 4, 2019 at 23:44
@IgorDragushhak Sure if you only want the permutations. It is great at that. — Dan D.
– Dan D., Commented Feb 5, 2019 at 1:13
Any recommendations on how can I modify my function so instead of printing the permutations they are stored in a list of list or a dictionary? — user3671704
– user3671704, Commented Jul 25, 2019 at 21:40

darij grinberg · Accepted Answer · 2019-02-08 03:16:07Z

1

Yes, your method is correct. Rather than prove this directly, you should prove that

(1) the execution of permute(a, l, r) returns each permutation of the l-th till r-th letters of a exactly once and exits with a being equal to what it was at the start of the execution.

This is straightforward to prove by induction on r - l. Without the "exits with a being equal" part of the claim, it would be hard.

As for the signs being right, this is just a loop invariant: Every time you swap two distinct entries, you multiply the sign by -1, and these are the only times you change the sign. So yes, the 0-th entry is the sign of the permutation at each time in your process.

Knuth's TAoCP (Volume 4A) has its Section 7.2.1.2 devoted to algorithms generating all permutations. Some of them can be easily modified to generate their signs, too. I'm wondering if yours is among them.

answered Feb 8, 2019 at 3:16

darij grinberg

1968 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3671704 Over a year ago

I did not know about Knuth's TAoCP book. I will take a look at it. Thanks for the info

darij grinberg Over a year ago

@user3671704: You can still find an old version of Section 7.2.1.2 on Knuth's website, by the way (pre-fascicle 2B).

Collectives™ on Stack Overflow

Heap's algorithm with permutation signature

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related