|
|
 |
|
Title: permutation
Submitter: Gagan Saksena
(other recipes)
Last Updated: 2001/08/05
Version no: 1.0
Category:
Algorithms
|
|
|
Description:
A small but efficient recursive function for printing the permutation of characters in a given string.
Source: Text Source
__version__ = "1.1"
"""permute.py-- A small but efficient recursive function for printing the
permutation of the characters of the specified string.
"""
import sys
def printList(alist, blist=[]):
if not len(alist): print ''.join(blist)
for i in range(len(alist)):
blist.append(alist.pop(i))
printList(alist, blist)
alist.insert(i, blist.pop())
if __name__ == '__main__':
k='love'
if len(sys.argv)>1: k = sys.argv[1]
printList(list(k))
Discussion:
Done initially as a programming excercise this script uses stacks to build the permutations of the characters in the specified string. This does not check for duplicate characters in the specified string but could be modified easily to do so too. Even though the algorithm above uses text/strings as an example, this can easily be used to work with lists of any sort.
I also plan to submit one that does combinations.
|
|
Add comment
|
|
Number of comments: 3
A faster way, Robin Houston, 2001/09/13
If you're generating the permutations of a long list, speed matters a lot. The code below is about four times faster than the recipe presented above.
def permute(alist, level=0):
index, copy, printing = level, list(alist), level+1 == len(alist)
while 1:
if printing:
print ''.join(copy)
else:
permute(copy, 1+level);
if index != 0:
copy[index-1], copy[index] = copy[index], copy[index-1]
index -= 1
if index If you're generating the permutations of a long list, speed matters a lot. The code below is about four times faster than the recipe presented above.
def permute(alist, level=0):
index, copy, printing = level, list(alist), level+1 == len(alist)
while 1:
if printing:
print ''.join(copy)
else:
permute(copy, 1+level);
if index != 0:
copy[index-1], copy[index] = copy[index], copy[index-1]
index -= 1
if index
Add comment
A different way using generators, Shalabh Chaturvedi, 2004/11/09
The logic behind generating permutations is a little more visible in the following (IMO):
def getPermutations(a):
if len(a)==1:
yield a
else:
for i in range(len(a)):
this = a[i]
rest = a[:i] + a[i+1:]
for p in getPermutations(rest):
yield this + p
Add comment
mutable default argument, Eyal Lotem, 2007/05/05
Its best to avoid those by using:
def ...(...blist=None...):
if blist == None:
blist = []
...
Or otherwise, this function can only run once in parallel and is not reentrant and not safe (when using threads, or if callbacks eventually re-call it).
Add comment
|
|
|
|
|
|
|
