Prelude
Позволяет указать другой способ решения вашей проблемы, который не связан с линейной алгеброй, но все еще полагается на теорию графов.
Представление
Естественное представление вашей проблемыГрафик, как показано ниже:
И эквивалентен:
Мы можем представить этот график с помощью словаря:
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],
}
Такая структура избавит вас от необходимости писать if операторов.
Матрица смежности
Представленное выше представление содержит ту же информацию, что и матрица смежности.Более того, мы можем сгенерировать его из приведенной выше структуры (преобразование логической разреженной матрицы в интегральную матрицу):
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
Где A - Матрица смежности, определенная в другой ответ .
Рекурсия
Теперь мы можем сгенерировать все телефонные номера, используя рекурсию:
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
Затем создаем список телефонных номеров:
plist = phoneNumbers(n=10, i=2)
Возвращает:
['2727272727',
'2727272729',
'2727272760',
'2727272761',
'2727272767',
...
'2949494927',
'2949494929',
'2949494940',
'2949494943',
'2949494949']
Теперь нужно просто взять длину списка:
len(plist) # 1424
Проверки
Мы можем проверить, нет ли дубликатов:
len(set(plist)) # 1424
Мы можем проверить, что наблюдение, которое мы сделали относительно последней цифры в другом ответе, все еще сохраняется в этой версии:
d = set([int(n[-1]) for n in plist]) # {0, 1, 3, 7, 9}
Номера телефонов не могут заканчиваться на:
set(range(10)) - d # {2, 4, 5, 6, 8}
Сравнение
Этот второй ответ:
- Не требует
numpy (нет необходимости в линейной алгебре), он использует только стандартную библиотеку Python; - Использует ли представление Graph, потому что это естественное представление вашегопроблема;
- Генерирует все номера телефонов перед их подсчетом, предыдущий ответ не генерировал все из них, у нас были только данные о числах в форме
x********y; - Использует рекурсию для решенияпроблема и, кажется, имеет экспоненциальную временную сложность, , если нам не нужно генерировать телефонные номера, мы должны использовать версию Matrix Power .
Benchmark
Сложность рекурсивной функции должна быть ограничена между O(2^n) и O(3^n), поскольку дерево рекурсии имеет глубину n-1 (и все ветви имеют одинаковую глубину), и каждый внутренний узел создает минимум 2 ребра и максимально3 ребра.Методология здесь не разделяй и властвуй алгоритм, это комбинаторика строковый генератор, поэтому мы ожидаем, что сложность будет экспоненциальной.
Сравнительный анализ двух функцийкажется, подтверждают это утверждение:
Рекурсивная функция демонстрирует линейное поведение в логарифмическом масштабе, что подтверждает экспоненциальную сложность и ограничено, как указано.Хуже того, в дополнение к вычислениям, для хранения списка потребуется растущий объем памяти.Я не смог пройти дальше, чем n=23, тогда мой ноутбук завис до того, как MemoryError.Лучшая оценка сложности - O((20/9)^n), где основание равно среднему значению степеней вершин (несвязанные вершины игнорируются).
Кажется, что метод Matrix Power имеет постоянное время по сравнению сразмер проблемы n.В документации numpy.linalg.matrix_power нет подробностей реализации, но это известная проблема собственных значений .Поэтому мы можем объяснить, почему сложность кажется постоянной до n.Это потому, что форма матрицы не зависит от n (она остается матрицей 10x10).Большая часть времени вычислений отводится для решения проблемы собственных значений , а не для повышения диагональной матрицы собственных значений до n-й степени , которая является тривиальной операцией (и единственной зависимостью от n).Вот почему это решение работает с «постоянным временем».Более того, для хранения Матрицы и ее разложения также потребуется квазипостоянный объем памяти, но это также не зависит от n.
Bonus
Найдите ниже код, используемый дляэталонные функции:
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,:])