Project Euler Problem 24 Ordering Numbers Having Non-Repeating Digits

[root@www ~]# python cartesian.py
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
Started at: Sat Sep 20 16:00:06 2008 Ended at: Sat Sep 20 16:00:33 2008
[root@www ~]# cat cartesian.py
# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()

class UniqueProduct:
"""A list of permutations used to solve problem 24.
9! is 362880. That means that there are 362880 10 digit numbers
in which each digit appears only once and the first digit is 0. The
same applies to such numbers in which the first digit is 1 or 2.

When ordered, the 0s precede the 1s and 2s. Therefore, the first
through 2 * 362880 numbers begin with 0 or 1. The millionth number
is the 1000000 - 2 * 362880 = 274240th number which begins with 2.

Therefore we know that the first digit of the answer is two, and
that a two cannot appear again. This makes our calculations easier.
We find the 274240th unique-digits number formed out of the list
[0,1,3,4,5,6,7,8,9]. That is our answer.
"""

def __init__(self,A,B):
"""
>>> A = [[i] for i in range(10)]
>>> B = A
>>> u = UniqueProduct(A,B)
>>> len(u.permutationList)
90
>>> A = [[1, 4],[3,5]]
>>> B = [[i] for i in range(10)]
>>> u = UniqueProduct(A,B)
>>> len(u.permutationList)
16


"""

self.permutationList = []
for n in uniqueCartesianProduct(A,B):
self.permutationList += [n]


def testForUniqueness(a,b):
"""Tests whether any element of row a has
value of singleton vector b
>>> a = [1,2,3]
>>> b = [1]
>>> testForUniqueness(a,b)
False
>>> b = [0]
>>> testForUniqueness(a,b)
True

"""
for ii in range(len(a)):
if a[ii] == b[0]:
return False
return True

def uniqueCartesianProduct(A,B):
for i in range(len(A)):
for j in range(len(B)):
if testForUniqueness(A[i],B[j]):
yield A[i] + B[j]

B = [[0],[1],[3],[4],[5],[6],[7],[8],[9]]
M1 = B
u = UniqueProduct(M1,B)
M2 = u.permutationList
u = UniqueProduct(M2,B)
M3 = u.permutationList
u = UniqueProduct(M3,B)
M4 = u.permutationList
u = UniqueProduct(M4,B)
M5 = u.permutationList
u = UniqueProduct(M5,B)
M6 = u.permutationList
u = UniqueProduct(M6,B)
M7 = u.permutationList
u = UniqueProduct(M7,B)
M8 = u.permutationList
u = UniqueProduct(M8,B)
M9 = u.permutationList
# The 274240th number has the index 2742439.
print([2] + M9[274239])








print "Started at: ", starttime, " Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()