euler-problems/euler24.py at main · kaesluder/euler-problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import numpy

def step1(sourceList):
    """Find the largest index k such that a[k] < a[k + 1].
    If no such index exists, the permutation is the
    last permutation."""
    a = None
    for k in xrange(len(sourceList)-1):
        if sourceList[k] < sourceList[k+1]:
            a = k

    return a


def step1a(sourceList):
    """Find the largest index k such that a[k] < a[k + 1].
    If no such index exists, the permutation is the
    last permutation."""
    a = None

    #working backwards over the loop is a marginal
    #optimization
    for k in xrange((len(sourceList)-1),0,-1):
        if sourceList[k-1] < sourceList[k]:
            return k-1
    return a


def step2(sourceList,a):
    """Find the largest index l such that a[k] < a[l].
    Since k + 1 is such an index, l is well defined and
    satisfies k < l."""
    b = 0
    for k in xrange((len(sourceList)-1),0,-1):
        if sourceList[a] < sourceList[k]:
            return k
    return b

def step3(sourceList,a,b):
    """Swap a[k] with a[l]."""
    returnList = sourceList
    x = sourceList[a]
    y = sourceList[b]
    returnList[b] = x
    returnList[a] = y
    return returnList

def step4(sourceList,a):
    """Reverse the sequence from a[k + 1] up to and including
    the final element a[n]."""
    returnList = sourceList
    x = returnList[:a+1]
    y = returnList[a+1:]
    y.reverse()
    returnList = x + y
    return returnList


def nextPermutation(sourceList):
    """combine all the steps to produce the next iteration
    in the cycle"""
    workingList = list(sourceList)
    a = step1a(workingList)


    #if a = None, then the list is maximally
    #sorted and there no next lex. continuation.

    if a == None:
        return None
    b = step2(workingList,a)
    workingList = step3(workingList,a,b)
    workingList = step4(workingList,a)
    return workingList


def getAllPermutations(sourceList):
    results = []
    #results.append(sourceList)
    next = list(sourceList)
    #print next
    while next != None:
        #print next
        results.append(list(next))
        next = nextPermutation(next)

    return results

def getToMillion(sourceList):
    next = list(sourceList)
    for x in xrange(1000000-1):
        next = nextPermutation(next)
    return next


#print nextPermutation([4,3,2,1])
print "".join([str(x) for x in getToMillion(range(10))])