fork download
copy 
  1. # -*- coding: utf-8 -*-
  2. # Python 2.7
  3. '''From here: http://stackoverflow.com/questions/4250125/generate-permutations-of-list-with-repeated-elements
  4. and here: http://b...content-available-to-author-only...n.se/2008/04/lexicographic-permutations-using.html
  5. This version is 3.5 times slower than the version working directly with indexes'''
  6.  
  7. from __future__ import print_function
  8. from itertools import izip
  9.  
  10.  
  11. def lexicographic_permutations(seq):
  12.     """Algorithm L for The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations."""
  13.  
  14.     def reverse(seq, start, end):
  15.         '''In-place reversion. Start and end denote the indexes of the last and the first element'''
  16.  
  17.         while start < end:
  18.             seq[start], seq[end] = seq[end], seq[start]
  19.             start += 1
  20.             end -= 1
  21.  
  22.  
  23.     def pairwise_reversed_enumerated(L):
  24.         "(a,b,c,d) -> ((2,c),(3,d)), ((1,b),(2,c)), ((0,a),(1,b))"
  25.         length = len(L)
  26.         a1 = izip(xrange(length-1,-1,-1),reversed(L))
  27.         a2 = izip(xrange(length-1,-1,-1),reversed(L))
  28.         next(a1, None)
  29.         return izip(a1, a2)
  30.  
  31.  
  32.     def reversed_enumerated(L):
  33.         '(a,b,c,d) -> (3,d), (2,c), (1,b), (0,a)'
  34.         return izip(xrange(len(L)-1,-1,-1),reversed(L))
  35.  
  36.  
  37.     #[Some checks]
  38.     if not seq:
  39.         raise StopIteration
  40.  
  41.     try:
  42.         seq[0]
  43.     except TypeError:
  44.         raise TypeError("seq must allow random access.")
  45.     #[end checks]
  46.  
  47.     last = len(seq)-1
  48.     seq = seq[:] #copy the input sequence
  49.  
  50.     yield seq #return the seq itself as a first value
  51.  
  52.     while True:
  53.         for ((i1,a1),(i2,a2)) in pairwise_reversed_enumerated(seq):
  54.             if a1 < a2:
  55.                 for (l,val) in reversed_enumerated(seq):
  56.                     if a1 < val:
  57.                         seq[i1], seq[l] = seq[l], seq[i1]
  58.                         break
  59.                 reverse(seq, i2, last)
  60.                 yield seq[:] # Change to yield references to get rid of (at worst) |seq|! copy operations.
  61.                 break
  62.         else: #this part will only run when there were no 'break' inside the for-loop
  63.             break #at this position there is no a1<a2, so we have reached the finish, so breaking out of the outer loop
  64.  
  65.  
  66. if __name__ == '__main__':
  67.     import timeit
  68.     #use 'pass' instead of 'print(p)' to get rid of hefty print function time complexity charges.
  69.     t = timeit.Timer(stmt='for p in lexicographic_permutations(range(9)): pass',setup='from __main__ import lexicographic_permutations')
  70.     print(t.timeit(number=1))
  71.  
  72.  
  73.  
Success #stdin #stdout 4.4s 6736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4.39087510109
https://ideone.com/mvu1y
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!