generating permutations :-)
Andreas Leitgeb
Andreas.Leitgeb at siemens.at
Mon Aug 5 17:54:05 CEST 2002
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/>
More information about the Python-list
mailing list