0

There's a question in my assignment that involves arrays and for loops.

The question asks you to find the value of int(m[3,4]).

import numpy as np

m = np.zeros((20,20))

for i in range(1,20):
  for j in range(1,20):
    m[i,j] = m[i-1,j]+m[i,j-1]+ 1

print(int(m[3,4]))

I've tried writing out all the values of m[i, j] for i and j in range 0 to 5 to find m[3,4], but I'm wondering if there's a shorter way of doing things?

The expected answer is 34.

fafl
  • 7,222
  • 3
  • 27
  • 50
entrynotfound
  • 17
  • 2
  • Is this a question? You already posted code that quickly solves this problem. – fafl Sep 12 '19 at 15:14
  • Yes so this question is actually for a written test where we don't have access to IDLE (so everything will have to be done on pen and paper). I'm just trying to see if there's a way where you don't have to work out literally every value of m[i,j] where i and j are <= 4. – entrynotfound Sep 12 '19 at 15:16
  • hint: n choose k minus 1 – Andrew Allen Sep 12 '19 at 15:44

4 Answers4

2

This is just pascals triangle with terms minus 1.

Complexity is therefore the same as finding n choose k.

Is there a math nCr function in python?

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom

With this, 

m[i, j] = ncr(i+j, i) - 1
Andrew Allen
  • 6,512
  • 5
  • 30
  • 73
  • given that OP says "on pen and paper" it might be OK to use the version that uses factorials explicitly, which is `(i+j)! / i! / j! - 1` where `!` is the [`factorial` function](https://docs.python.org/3/library/math.html#math.factorial) – Sam Mason Sep 13 '19 at 09:13
0

Another solution:

Python 3.8.0b4 (default, Sep  5 2019, 14:10:43)
Type 'copyright', 'credits' or 'license' for more information
IPython 7.8.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import numpy as np

In [2]: N = 20

In [3]: m = np.zeros((N, N), int)

In [4]: x = m[:]

In [5]: for i in range(1, N):
   ...:     for j in range(1, N):
   ...:         m[i, j] = m[i - 1, j] + m[i, j - 1] + 1
   ...:

In [6]: for i in range(1, N):
   ...:     x[i] = [sum(x[i - 1, :j]) + j for j in range(N)]
   ...:

In [7]: (m == x).all()
Out[7]: True
Waket Zheng
  • 5,065
  • 2
  • 17
  • 30
0

For all i,j in the range 1 to 20 is 400 terms. You can find the answer by calculating 12 terms

Here's the matrix: 

a-----b-----c-----d

e-----f-----g-----h

i-----j-----k-----l

m-----n-----o-----p

Each term is the sum of the adjacent left and above plus 1. For example k = j + g + 1

Now walk your way through the matrix. For i,j = 1,1 the first 2 terms zero out, so a = 1,

All terms to the right or below a a just plus 1. Now we have:

1-----2-----3-----4

2-----f-----g-----h

3-----j-----k-----l

4-----n-----o-----p

Now 

f = 2 + 2 + 1 = 5
g = 5 + 3 + 1 = 9

keep going to get:

1-----2-----3-----4

2-----5-----9-----14

3-----9-----19-----34<--

m-----n-----o-----p
georg
  • 211,518
  • 52
  • 313
  • 390
dLip11
  • 1
  • 1
0

I suggest writing out an example, and finding the pattern. Printing the resulting 5x5 matrix, you'll see

[[ 0.  0.  0.  0.  0.]
 [ 0.  1.  2.  3.  4.]
 [ 0.  2.  5.  9. 14.]
 [ 0.  3.  9. 19. 34.]
 [ 0.  4. 14. 34. 69.]]

Notice that the matrix is symmetric, i.e. m[i,j] == m[j,i]. From this, you will know that you only need to do half the number of calculations. You can find either the lower or upper triangular matrix first, and then you'll have your answer via symmetry.

natn2323
  • 1,983
  • 1
  • 13
  • 30