DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Another Pyrex Permutation Generator

08.02.2006
| 4055 views |
  • submit to reddit
        // description of your code here

cdef class PermuteJ:

   cdef int n, first
   cdef int lst3[32]
   cdef object lst, lst2

   def __init__(self, lst):
       cdef int i
       self.lst = lst
       self.lst2 = lst[:]
       self.first = 0
       self.n = len(lst) - 1
       if self.n >= 31:
           raise Exception, "Are you kidding?"
       for i from 0 <= i < len(lst):
           self.lst3[i] = i

   def __iter__(self):
       return self

   def __next__(self):
       cdef int j, l, k, x, y, z, sn, length, neg1, neg2, neg3
       cdef int* sl
       cdef object output

       if self.first == 0:
           self.first = 1
           return self.lst2
       if self.n == 1:
           return [self.lst[1], self.lst[0]]

       sn = self.n
       length = sn + 1
       sl = self.lst3
       neg1 = sn
       neg2 = length - 2
       neg3 = length - 3
       while 1:
           if sl[neg2] < sl[neg1]:
               sl[neg2], sl[neg1] = sl[neg1], sl[neg2]
           elif sl[neg3] < sl[neg2]:
               if sl[neg3] < sl[neg1]:
                   sl[neg3], sl[neg2], sl[neg1] = sl[neg1], sl[neg3], sl[neg2]
               else:
                   sl[neg3], sl[neg2], sl[neg1] = sl[neg2], sl[neg1], sl[neg3]
           else:
               j = sn - 3
               if j < 0: raise StopIteration
               y = sl[j]
               x = sl[neg3]
               z = sl[neg1]
               while y >= x:
                   j = j - 1
                   if j < 0: raise StopIteration
                   x = y
                   y = sl[j]
               if y < z:
                   sl[j] = z
                   sl[j+1] = y
                   sl[sn] = x
               else:
                   l = neg2
                   while y >= sl[l]:
                       l = l - 1
                   sl[j], sl[l] = sl[l], y
                   sl[sn], sl[j+1] = sl[j+1], sl[sn]
               k = j + 2
               l = neg2
               while k < l:
                   sl[k], sl[l] = sl[l], sl[k]
                   k = k + 1
                   l = l - 1

           lst = self.lst
           lst2 = self.lst2
           for j from 0 <= j < length:
               lst2[j] = sl[j]

           return lst2