P.S. – This Post is intended for people who want to know a simple,efficient approach to generate all possible permutations for a sequence.For real world software I would recommend using standard library functions.
All of us at some moment while coding have faced the problem on how to generate all possible permutations of a sequence.
In this case algorithm’s efficiency becomes highly important. Use a recursive solution and for even moderately sized sequence, running time (and memory) goes though the roof.
Recently I came across Donald knuth’s elegant linear time non-recursive approach. I wanted to see algorithm in action, so I implemented it and thought it would be nice to write a blog post about it.
So Without further ado, I have given below a simple explanation of algorithm working, and code implementation in both java,python.
The idea is to generate permutations of the sequence so given, in lexicographical increasing order.
for ex. for an array [1,2,4,3]
Resulting Permutations would be [1,2,3,4], [1,2,4,3] …. [4,3,2,1]
One approach on how to generate this ordered permutation can be read from its wikipedia entry.
Python implementation (Download code):
def getNextPermute(arr): """ Implementation of http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations Algorithm to effeciently generate permutations of a sequence returns a generator type object, which for each call return next possible permutation until all possiblities are exhausted """ arr.sort() yield arr[:] while True: for j in xrange(len(arr)-2,-1,-1): #find larget a[j] if arr[j+1] > arr[j]: break else: return for l in xrange(len(arr)-1,j,-1): #find larget a[j] if arr[l] > arr[j]: break arr[j],arr[l] = arr[l],arr[j] #swap a[j],a[l] arr[j+1:] = arr[j+1:][::-1] #reverse array present after the index (j+1)th yield arr[:] if __name__=="__main__": assert len(list(getNextPermute([5,1,2,3,4]))) == 120 for each in getNextPermute(["a","b","c"]): print ','.join(each)
Java Implementation (Download Code):