Создание треугольника Паскаля в словаре - PullRequest
Новая
       28

Создание треугольника Паскаля в словаре

0 голосов
/ 07 ноября 2018

Я пытаюсь создать функцию, которая возвращает словарь, описывающий треугольник Паскаля.

Например, 

pascal(3)

даст мне 

{1: [1], 2: [1,1], 3: [1,2,1]}

В настоящее время я знаю, как создать функцию, которая возвращает список элементов. в определенной строке для n, равного или превышающего 2 

def pascal(n):
 if n == 0:
    return {}
 elif n == 1:
    return {1:[1]}
 else:
    row = [1] + [list(pascal(n-1))[i] + list(pascal(n-1))[i+1] for i in range(n-2)] + [1]
    return row

С этой функцией 

pascal(3)

дает мне 

[1,2,1]

Можно ли изменить мою функцию таким образом, чтобы 

pascal(3)

возвращает желаемый результат 

{1: [1], 2: [1,1], 3: [1,2,1]}

Буду признателен за любую помощь.

Ответы [ 5 ]

0 голосов
/ 07 ноября 2018

Вы можете использовать замыкание с рекурсией: 

def pascal(n:int) -> dict:
  def _pascal(_s, _e, _last, _base={1:[1], 2:[1, 1]}):
    return _last if not _e-_s else _pascal(_s+1, _e, {**_last, **{_s:_base.get(_s, [1, *[_last[_s-1][i]+_last[_s-1][i+1] for i in range(len(_last)-1)], 1])}})
  return _pascal(1, n+1, {})

print(pascal(3))

Выход: 

{1: [1], 2: [1, 1], 3: [1, 2, 1]}
0 голосов
/ 07 ноября 2018

Вы можете сделать это быстро, создавая свой диктат в качестве побочного эффекта: 

_cache = {}

def pascal(n):
    try:
        result = _cache[n]
    except KeyError:
        if n == 0:
            result = []
        elif n == 1:
            result = [1]
        else:
            previous = pascal(n - 1)
            result = [1] + [previous[i] + previous[i + 1] for i in range(n - 2)] + [1]
        _cache[n] = result
    return result

pascal(500)

print(_cache)

Вам не нужно вычислять pascal(n) более одного раза: это не так, как будто оно меняется. Так что запомните, каким был ваш окончательный ответ, сохранив его в словаре кэширования, в первую очередь, словарь, который вы на самом деле хотели.

Для создания словаря на моем ноутбуке требуется около 0,08 с.

0 голосов
/ 07 ноября 2018

Вы можете использовать zip, чтобы связать возвращаемый список из рекурсивного вызова с тем же списком, но с одним индексом, дополненным 0: 

def pascal(n):
    if n == 1:
        return {1: [1]}
    p = pascal(n - 1)
    p[n] = list(map(sum, zip([0] + p[n - 1], p[n - 1] + [0])))
    return p

так что: 

for n in range(1, 6):
    print(pascal(n))

выходы: 

{1: [1]}
{1: [1], 2: [1, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1], 5: [1, 4, 6, 4, 1]}
0 голосов
/ 07 ноября 2018

Я бы осторожно использовал такую ​​рекурсию - это очень неэффективно. Вы вызываете функцию дважды в цикле в теле функции. Важно подумать, сколько раз функция будет вызываться для оценки определенных значений n.

Очевидно, что когда n = 1, функция вызывается один раз.

Когда n = 2, функция вызывается один раз, а затем функция вызывает себя дважды, всего 3 вызова.

При n = 3 функция вызывается один раз, затем функции вызывают себя дважды, а затем каждый из этих двух вызовов вызывает функцию четыре раза ... Так что это 11 вызовов.

Так что количество звонков numCalls = 1 + 2 + 2*4 + 2*4*6 + ... + 2*4*6*...*2n)

Эта последовательность очень быстро растет ... Когда n равно 20, это 1308293051285742128434781. Вызовы

Рекурсия не всегда злая, вам просто нужно быть осторожным, это решение вызывает себя n раз: 

    def genPascalDict(nMax):
        if nMax < 2:
            return {1: [1]}
        else:
            pascalDict = genPascalDict(nMax - 1)
            lastRow = pascalDict[nMax - 1]
            pascalDict[nMax] = [1] + [lastRow[n + 1] + lastRow[nMax - n - 2] for n in range(nMax - 2)] + [1]
            return pascalDict
0 голосов
/ 07 ноября 2018

Если вы открыты для итеративного решения, я подготовил следующее. 

from itertools import chain 

def pascal(n):
    pad = (0,)
    result = {1: [1]}
    for i in range(2, n + 1):
        previous = list(chain(pad, result[i - 1], pad))
        result[i] = [sum(pair) for pair in zip(previous, previous[1:])]
    return result

Демо-версия: 

>>> for n in range(1, 6):
...:    print(pascal(n))
...:    
...:    
{1: [1]}
{1: [1], 2: [1, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1]}
{1: [1], 2: [1, 1], 3: [1, 2, 1], 4: [1, 3, 3, 1], 5: [1, 4, 6, 4, 1]}

С немного большим количеством строк, но также и более эффективным использованием памяти: 

from itertools import chain, tee

def pascal(n):
    pad = (0,)
    result = {1: [1]}
    for i in range(2, n + 1):
        previous = chain(pad, result[i - 1], pad)
        c1, c2 = tee(previous)
        next(c2)
        result[i] = [sum(pair) for pair in zip(c1, c2)]
    return result

Наконец, наличие dict с последовательными целочисленными ключами не очень полезно, вы можете просто использовать список, в который вы индексируете, начиная с 0. Окончательное решение: 

def pascal(n):
    pad = (0,)
    result = [[1]]
    for i in range(1, n):
        previous = chain(pad, result[i - 1], pad)
        c1, c2 = tee(previous)
        next(c2)
        result.append([sum(pair) for pair in zip(c1, c2)])
    return result

Демо-версия: 

>>> for n in range(1, 6):
...:    print(pascal(n))
...:    
[[1]]
[[1], [1, 1]]
[[1], [1, 1], [1, 2, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

edit: улучшена эффективность за счет отсутствия двух кортежей за итерацию, достаточно создать экземпляр pad один раз.

...