generating permutations :-)

[Andreas Leitgeb]

When I read in my book about the generators in Python,
I couldn't help but try out this feature, by translating
some of my old C-code (which used callbacks instead):

It shows that generators can be built recursively :-)

--- snip ---
from __future__ import generators
def perm(arr,N=None):
  if N is None: N=len(arr)-1
  if N>1:
    for i in perm(arr,N-1): yield i
  else: yield arr
  for k in range(N):
    if N&1: (arr[N] , arr[k]) = (arr[k], arr[N])
    else:   (arr[N] , arr[0]) = (arr[0], arr[N])
    if N>1:
      for i in perm(arr,N-1): yield i
    else: yield arr
--- snip ---

examples:      
x=perm([perm,42,'Hallo'])
#x=perm([0,1,2])
for i in x : print i

# caveat:
allperms=[list(i) for i in perm([1,2,3])]   # ok
allperms=[i for i in perm([1,2,3])] # wrong: 
  # will contain n! copies of the last permutation

Between two iterations, exactly one transposition of two 
elements takes place.
Permutations of lists of more than 10 elements tend to take 
their time ...  (at least on my machine)

PS: I made up the algorithm myself, although it may already
  have been generally known before :-)
 I've not yet attempted to formally proove its correctness, 
  but it gave me plausible results for the tests that I made.

PPS: the conditions of the if's inside the loop do indeed 
 NOT depend on the loop-variable. This is not a typo.

PPPS: this was the prog I had in mind when asking for 
 "call-by-ref" in another thread.  Since the argument
 in question is a list itself, I didn't need to embed it
 into a list or object.

-- 
Newsflash: Sproingy made it to the ground !
  read more ... <http://avl.enemy.org/sproingy/>