Finding Longest Geometric Progression in an Array

Question

I'm trying to implement a dynamic programming algorithm to find the length of the longest geometric progression in a list. I came across this algorithm: http://www.cs.illinois.edu/~jeffe/pubs/pdf/arith.pdf and tried to modify it for geometric progression. However, I cannot get it to work.

My code is:

def dp(numbers):
  numbers = sorted(numbers)

  n = len(numbers)
  table = [[2] * n] * n
  for i in range(n):
    table[i][n - 1] = 2

  largest = 2
  for j in range(n - 1, -1, -1):
    i = j - 1
    k = j + 1
    while i >= 0 and k <= n - 1:
      if numbers[j] > math.sqrt(numbers[i] * numbers[k]):
        k += 1
      elif numbers[j] < math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = 2
        i -= 1
      elif numbers[j] == math.sqrt(numbers[i] * numbers[k]):
        table[i][j] = table[j][k] +  1
        largest = max(largest, table[i][j])
        i -= 1
        k += 1

    while i >= 0:
      table[i][j] = 2
      i -= 1

  return largest

For example, if I run print dp([1, 2, 4, 8, 16, 32, 64]) I get 4 when it should be 7. Any help on what I'm doing wrong would be really helpful.

Answer 1

The problem is here:

table = [[2] * n] * n

What this does is make a list consisting of one n-element list n times. The problem is that, since these are the same (is-same, not just ==-same) list and not copies, they all get updated together, which is bad, e.g.,

>>> lst=[[2]]*2
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
True
>>> lst[0][0]=1
>>> lst
[[1], [1]]

The fix is to write

table = [[2] * n for i in range(n)]

which runs [2] * n repeatedly to obtain n copies, which initially are ==-same but not is-same.

>>> lst=[[2]for i in range(2)]
>>> lst
[[2], [2]]
>>> lst[0]==lst[1]
True
>>> lst[0]is lst[1]
False
>>> lst[0][0]=1
>>> lst
[[1], [2]]

EDIT: Also, for j in range(n - 1, -1, -1): should be for j in range(n - 2, -1, -1): to match the pseudocode exactly, though this is not the cause of the bug.