Prelude
Lets state another way to solve your problem that does not involve Linear Algebra but still rely on Graph Theory.
Representation
A natural representation of your problem is a Graph as shown below:
And is equivalent to:
We can represent this Graph by a dictionary:
G = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [0, 3, 9],
5: [], # This vertex could be ignored because there is no edge linked to it
6: [0, 1, 7],
7: [2, 6],
8: [1, 3],
9: [2, 4],
}
This kind of structure will spare you the need of writing if statements.
Adjacency Matrix
The representation above contains the same information than the Adjacency Matrix. Further more, we can generate it from the structure above (conversion of a Boolean Sparse Matrix into an Integral Matrix):
def AdjacencyMatrix(d):
A = np.zeros([len(d)]*2)
for i in d:
for j in d[i]:
A[i,j] = 1
return A
C = AdjacencyMatrix(G)
np.allclose(A, C) # True
Where A is the Adjacency Matrix defined in the another answer.
Recursion
Now we can generate all phone numbers using recursion:
def phoneNumbers(n=10, i=2, G=G, number='', store=None):
if store is None:
store = list()
number += str(i)
if n > 1:
for j in G[i]:
phoneNumbers(n=n-1, i=j, G=G, number=number, store=store)
else:
store.append(number)
return store
Then we build the phone numbers list:
plist = phoneNumbers(n=10, i=2)
It returns:
['2727272727',
'2727272729',
'2727272760',
'2727272761',
'2727272767',
...
'2949494927',
'2949494929',
'2949494940',
'2949494943',
'2949494949']
Now it is just about taking the length of the list:
len(plist) # 1424
Checks
We can check there is no duplicates:
len(set(plist)) # 1424
We can check than the observation we have made about last digit in the another answer still holds in this version:
d = set([int(n[-1]) for n in plist]) # {0, 1, 3, 7, 9}
Phone numbers cannot end with:
set(range(10)) - d # {2, 4, 5, 6, 8}
Comparison
This second answer:
- Does not require
numpy (no need of Linear Algebra), it makes only use of Python Standard Library;
- Does use a Graph representation because it is a natural representation of your problem;
- Generates all phone numbers before counting them, the previous answer did not generate all of them, we only had details on numbers in the form
x********y;
- Makes use recursion to solve the problem and seems to have an exponential time complexity, if we don't need the phone numbers to be generated we should use the Matrix Power version.
Benchmark
The complexity of recursive function should be bounded between O(2^n) and O(3^n) because the recursion tree has a depth of n-1 (and all branches has the same depth) and each inner node creates minimum 2 edges and at maximum 3 edges. The methodology here is not divide-and-conquer algorithm it is a Combinatorics string generator, this is why we expect the complexity to be exponential.
Benchmarking two functions seems to validate this claim:
The recursive function shows a linear behavior in logarithmic scale which confirms an exponential complexity and is bounded as stated. Worse, in addition with computation, it will require a growing amount of memory to store the list. I could not get any further than n=23, then my laptop freezes before having the MemoryError. A better estimation of complexity is O((20/9)^n) where the base is equal to the mean of vertices degrees (disconnected vertices are ignored).
The Matrix Power method seems to have a constant time versus the problem size n. There is no implementation details on numpy.linalg.matrix_power documentation but this is a known eigenvalues problem. Therefore we can explain why the complexity seems to be constant before n. It is because the matrix shape is independent of n (it remains a 10x10 matrix). Most of the computation time is dedicated to solve the eigenvalues problem and not to raise a diagonal eigenvalues matrix to the n-th power which is a trivial operation (and the only dependence to n). This why this solution performs with a "constant time". Further more, it will also requires a quasi constant amount of memory to store the Matrix and its decomposition, but this is also independent of n.
Bonus
Find below the code used to benchmark functions:
import timeit
nr = 20
ns = 100
N = 15
nt = np.arange(N) + 1
t = np.full((N, 4), np.nan)
for (i, n) in enumerate(nt):
t[i,0] = np.mean(timeit.Timer("phoneNumbersCount(n=%d)" % n, setup="from __main__ import phoneNumbersCount").repeat(nr, number=ns))
t[i,1] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=2))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
t[i,2] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=0))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
t[i,3] = np.mean(timeit.Timer("len(phoneNumbers(n=%d, i=6))" % n, setup="from __main__ import phoneNumbers").repeat(nr, number=ns))
print(n, t[i,:])
