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?