nth permutation in a lexicographical order

Problem:

Somebody is generating permutations of a given list of elements in a lexicographical order. What is the value of say nth permutation?

Brute force solution is to generate them all, but in that case you'll spend quite a lot of time generating useless permutations - O(n!). So here is the easy way:

	#!/bin/env python
	"""
	Solves a problem of getting permutation of a given index,
	while you know that permutations are created in a lexicographical order.
	As input you are specifying a list of elements and index of permutation you want to get.
	"""
	## imports
	from math import factorial
	## this one just for checking
	from itertools import permutations
	def getNthPermutation( pIndex, inList, outList=[] ):
	""" get :pIndex: permutation of :inList:
	:warn: permutations are sorted in lexicographical order starting from 0, i.e.:
	0 -> [1, 2, 3], 1 -> [1, 3, 2] and so on
	:param int pIndex: given permutation index
	:param list inList: initial list of elements
	:param list outList: result list
	"""
	## permutation index too big
	if pIndex >= factorial( len(inList) ): return []
	## no more elements to use
	if not inList: return outList
	## make sure eList is sorted
	inList.sort()
	## get factorial
	f = factorial( len(inList)-1 )
	index = pIndex / f
	reminder = pIndex % f
	## add new element to outList
	outList.append( inList[index] )
	## ...and remove it from inList
	del inList[index]
	## bail out or call recursively depending of the reminder
	if not reminder:
	return outList + inList
	else:
	return getNthPermutation( reminder, inList, outList )
	### test execution
	if __name__ == "__main__":
	ps = permutations( [1,2,3,4,5,6] )
	for i in range(factorial(6)):
	resList = []
	res = getNthPermutation( i, [1,2,3,4,5,6], resList )
	check = list( ps.next() )
	assert( res == check )

view raw perm.py hosted with ❤ by GitHub