Creating a Pascal triangle in a dictionary

3972 views python
5

I am trying to create a function that returns a dictionary that describes a pascal triangle.

For example,

pascal(3)

would give me

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

I currently know how to create a function that returns the list of elements in a certain row for n equal to or greater than 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

With this function,

pascal(3)

gives me

[1,2,1]

Is it possible to change my function in such a way that

pascal(3)

returns the desired result of

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

Any help would be appreciated.

answered question

are you open to having a list of lists instead of a dict? the keys of your dict are just line indices anyways

2 Answers

10

If you are open to an iterative solution, I cooked up up the following.

from itertools import chain 

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

Demo:

>>> for n in range(1, 7):
...:    print(pascal(n))
...:    
{1: [1]}
{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]}

posted this
11

Since you already have working function, all you have to do is loop over each row and append that to your dictionary. I changed n==0 to n<=0 so negative numbers won't mess up your function.

def pascal(n):
    if int(n) <= 0:
        return {}

    dict_pascal = {}
    for i in range(1, int(n)+1):
        if i == 1:
            dict_pascal[i] = [1]
        else:
            dict_pascal[i] = [1] + [list(pascal(i-1))[j] + list(pascal(i-1))[j+1] for j in range(n-2)] + [1]
     return dict_pascal

pascal(5) returns:

{1: [1], 2: [1, 1], 3: [1, 3, 1], 4: [1, 3, 5, 1], 5: [1, 3, 5, 7, 1]}

posted this

Have an answer?

JD

Please login first before posting an answer.

Ads

Categories