This time lets take it to pure mathematics, permutations. Permutation is an ordered arrangement of objects, for example, alphabets, numerical, words. In this session, I am dealing with the lexicographic order of listed numerical digits, problem from projecteuler. The problem requires the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, which took me two days to work on. Coming up with the solution was not that difficult, only that the function took along run time hence not efficient. The challenge was to develop a function that takes a short run time as possible, this is, less than 5 second.

Simpler solution, but takes along runtime.

p=permutations([0,1,2,3,4,5,6,7,8,9])
print p[10^6]
the function simply forms a lexicographic permutation of the list, then prints the millionth permutation
 Complex and efficient.
def lexicographicPermutations(N):
    currentTarget=10^6
    y=[] #postionlist
    d = range(0,N)
    l=N-1 #factorialValue
    answerList=[]
    while l>0:
        b=0
        while b<N:
            c =    b   *factorial(l) #Product for 10^6 summation
            cNext=(b+1)*factorial(l)
            if currentTarget-c>=0 and currentTarget-cNext<0:
                y.append(b)
                currentTarget=currentTarget-c
            b=b+1
        l=l-1
    i=0
    while i<N-1:
        answerList.append(d[y[i]])
        d.remove(d[y[i]])
        i=i+1
    answerList.append(d[0])
    print answerList
lexicographicPermutations(10)
 -The function takes the upper limit range as N,multiplies the factorials from the highest with b(constant which brings the value closer to the targeted number(10^6)). With b as the position order of the items in the list d, b is stored in the list y. The function then forms  a list answerList by adding the digits in the lexicographic order for the millionth permutation.
 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Some Maths Links

Vi Hart - Hyperactive videos about beautiful math concepts. Snowdecahedron - A mathematical art installation. Tau - An alternative to pi. BBC Brief History of Math - A Documentary. John Baez - A maths superhero.
Set your Twitter account name in your settings to use the TwitterBar Section.