A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
so: there are 3.6 million possible permutations. Order them lexigraphically. Return millionth one.
one = [0,1,2,3,4,5,6,7,8,9] #
two = [0,1,2,3,4,5,6,7,9,8] # 2 with 7 in pos9
three = [0,1,2,3,4,5,6,8,7,9] # 2 with 8 in pos9
four = [0,1,2,3,4,5,6,8,9,7]
five = [0,1,2,3,4,5,6,9,7,8]
six = [0,1,2,3,4,5,6,9,8,7]
"""
check if last two n1,n2 are s.t. n1<n2. if so, next one is n1/n2. If not, go to previous number.
check if there is a bigger number further to the right. if so, put the smallest bigger number in that place.
"""
import math
print math.factorial(10)
def permutize(inlist):
# take a list in the lexographically last position, and systematically go through other permutations (lex ordered)
# keep track of # of permutations; stop when n is reached
index=1
switcher = True
while switcher:
cut = -(index+1)
stock = inlist[cut:]
current = stock[0]
newlist = inlist[:cut]
sortedstock = sorted(stock)
for el in sortedstock:
if not el == current and el>current:
# take the first el of the sorted list, replace it with
newlist.append(el)
sortedstock.remove(el)
newlist += sortedstock
return newlist
else:
index += 1
print two == permutize(one)
print three == permutize(two)
print four == permutize(three)
print five == permutize(four)
practice = [5,2,3,4,1]
newlis = sorted(practice)
print practice
print newlis
def bruter(n, inputlist):
#take a list, and go through lex orderings until n is reached
iterations = 1
lst = inputlist
while iterations<n:
lst = permutize(lst)
iterations += 1
return lst
testcase = [0,1,2]
print bruter(1, testcase)
print bruter(3,testcase)
print bruter(1000000,one)