1  
   2  cdef class PermuteJ:
   3  
   4     cdef int n, first
   5     cdef int lst3[32]
   6     cdef object lst, lst2
   7  
   8     def __init__(self, lst):
   9         cdef int i
  10         self.lst = lst
  11         self.lst2 = lst[:]
  12         self.first = 0
  13         self.n = len(lst) - 1
  14         if self.n >= 31:
  15             raise Exception, "Are you kidding?"
  16         for i from 0 <= i < len(lst):
  17             self.lst3[i] = i
  18  
  19     def __iter__(self):
  20         return self
  21  
  22     def __next__(self):
  23         cdef int j, l, k, x, y, z, sn, length, neg1, neg2, neg3
  24         cdef int* sl
  25         cdef object output
  26  
  27         if self.first == 0:
  28             self.first = 1
  29             return self.lst2
  30         if self.n == 1:
  31             return [self.lst[1], self.lst[0]]
  32  
  33         sn = self.n
  34         length = sn + 1
  35         sl = self.lst3
  36         neg1 = sn
  37         neg2 = length - 2
  38         neg3 = length - 3
  39         while 1:
  40             if sl[neg2] < sl[neg1]:
  41                 sl[neg2], sl[neg1] = sl[neg1], sl[neg2]
  42             elif sl[neg3] < sl[neg2]:
  43                 if sl[neg3] < sl[neg1]:
  44                     sl[neg3], sl[neg2], sl[neg1] = sl[neg1], sl[neg3], sl[neg2]
  45                 else:
  46                     sl[neg3], sl[neg2], sl[neg1] = sl[neg2], sl[neg1], sl[neg3]
  47             else:
  48                 j = sn - 3
  49                 if j < 0: raise StopIteration
  50                 y = sl[j]
  51                 x = sl[neg3]
  52                 z = sl[neg1]
  53                 while y >= x:
  54                     j = j - 1
  55                     if j < 0: raise StopIteration
  56                     x = y
  57                     y = sl[j]
  58                 if y < z:
  59                     sl[j] = z
  60                     sl[j+1] = y
  61                     sl[sn] = x
  62                 else:
  63                     l = neg2
  64                     while y >= sl[l]:
  65                         l = l - 1
  66                     sl[j], sl[l] = sl[l], y
  67                     sl[sn], sl[j+1] = sl[j+1], sl[sn]
  68                 k = j + 2
  69                 l = neg2
  70                 while k < l:
  71                     sl[k], sl[l] = sl[l], sl[k]
  72                     k = k + 1
  73                     l = l - 1
  74  
  75             lst = self.lst
  76             lst2 = self.lst2
  77             for j from 0 <= j < length:
  78                 lst2[j] = sl[j]
  79  
  80             return lst2
  81  

   1  
   2  cdef class Permute2:
   3  
   4      cdef int n, first
   5      cdef object lst
   6  
   7      def __init__(self, lst):
   8          self.lst = lst
   9          self.first = 0
  10          self.n = len(lst) - 1
  11  
  12      def __iter__(self):
  13          return self
  14  
  15      def __next__(self):
  16          cdef int j, l, k, x, y, z
  17          if self.first == 0:
  18              self.first = 1
  19              return self.lst
  20          if self.n == 1:
  21              return [self.lst[1], self.lst[0]]
  22          while 1:
  23              if self.lst[-2] < self.lst[-1]:
  24                  self.lst[-2], self.lst[-1] = self.lst[-1], self.lst[-2]
  25              elif self.lst[-3] < self.lst[-2]:
  26                  if self.lst[-3] < self.lst[-1]:
  27                      self.lst[-3], self.lst[-2], self.lst[-1] = self.lst[-1], self.lst[-3], self.lst[-2]
  28                  else:
  29                      self.lst[-3], self.lst[-2], self.lst[-1] = self.lst[-2], self.lst[-1], self.lst[-3]
  30              else:
  31                  j = self.n - 3
  32                  if j < 0: raise StopIteration
  33                  y = self.lst[j]
  34                  x = self.lst[-3]
  35                  z = self.lst[-1]
  36                  while y >= x:
  37                      j = j - 1
  38                      if j < 0: raise StopIteration
  39                      x = y
  40                      y = self.lst[j]
  41                  if y < z:
  42                      self.lst[j] = z
  43                      self.lst[j+1] = y
  44                      self.lst[self.n] = x
  45                  else:
  46                      l = self.n - 1
  47                      while y >= self.lst[l]:
  48                          l = l - 1
  49                      self.lst[j], self.lst[l] = self.lst[l], y
  50                      self.lst[self.n], self.lst[j+1] = self.lst[j+1], self.lst[self.n]
  51                  k = j + 2
  52                  l = self.n - 1
  53                  while k < l:
  54                      self.lst[k], self.lst[l] = self.lst[l], self.lst[k]
  55                      k = k + 1
  56                      l = l - 1
  57              return self.lst