Common List Index Out Of Range Issue, Why?

Question

import scipy.special


s = [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3,
     1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4,
     1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3,
     1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5,
     1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3,
     1, 2, 1, 4, 1]


r = []

for n in range(20):
 result = 1
 for k in range(n-1):
     result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
 r.append(result)


def binomial_transform(sequence):
    n = len(sequence)
    result = [0] * n
    
    for i in range(n):
        for j in range(i+1):
            result[i] += sequence[j] * scipy.special.binom(i, j)
    
    return result

sequence = r
binomial_result = binomial_transform(sequence)
print(binomial_result)

I tried playing with where result began, 0 instead of 1, tried having r initialized with 1 as an element instead of it being empty, tried maybe instead of k in range n-1, k in range n.The code worked perfectly when the list, s, was the oeis sequence A000120, and it produced, as expected, oeis A101911. now that i changed it from A000120 to A001511 it says list index out of range. This has driven me crazy. If i just add another number to the front of s, it compiles without error, but if delete an element, there's an error.

If it's driving you crazy, start logging. You're getting the error on line 17, so: log `n` and `k` before that line. You'll see `n` is 2, `k` is 0, and `s[n - k - 1]` is 2. So: what size is `r` at this point? And what would you imagine happens when you try to access `r[2]`. — Mike 'Pomax' Kamermans, Aug 19 '23 at 19:09
Uh sorry i don't get it, what do you mean by logging? really appreciate the speedy response by the way — John Smith, Aug 19 '23 at 19:10
literally logging all the variables you're making use of. `print(n, k, s[n - k - 1], len(r))` because you can't solve a problem if you don't know the problem: log your variables, to start understanding the problem. — Mike 'Pomax' Kamermans, Aug 19 '23 at 19:11
oh awesome, you even mentioned it, there's an issue with r[2]. Though Im a bit stumped — John Smith, Aug 19 '23 at 19:20
Now you know the problem, work backwards: should `r` be bigger than 2 elements that at this point? Then look at the code in your loop to see where you're growing `r` and whether you did that correctly (because if things error, the conclusion we already have is that it's not). Should it _not_ be bigger? In that case, rethink what element you _should_ be accessing instead of `s[n - k - 1]`. — Mike 'Pomax' Kamermans, Aug 19 '23 at 19:22
Your inner loop doesn't run at all until `n == 2`. At that point the first iteration of the inner loop is `n - k - 1 == 1` then `s[1] == 2` and `r[2]` is an index error at this point. Because `r` is `[1, 1]` (from the first two outer loops where the inner loop didn't run). — Mark, Aug 19 '23 at 19:23
oh i think i got it, should i be accessing r[s[n - k - 1]-1]? — John Smith, Aug 19 '23 at 19:25
In your own words, where the code says `for j in range(i+1):`, what do you think will be the largest possible value of `j`? Do you expect that value to be a valid index for `sequence`? Why or why not? Given that `n` is the name you used for the length of `sequence`, in terms of `n`, what do you think are the valid indices for `sequence`? What do you think is the first valid index? What do you think is the last valid index? — Karl Knechtel, Aug 19 '23 at 19:56
Welcome to Stack Overflow. Please read [ask]. We do not find the bug for you here; we require a **specific** question - which will come out of your best attempt to [understand](//meta.stackoverflow.com/q/261592/) and [locate](//ericlippert.com/2014/03/05) a specific problem, and showcase it in a [mre]. When you say "This has driven me crazy.", I sympathize; but fixing problems is about *analyzing* them in an *organized* way - not about getting aggravated or experimenting without any plan. — Karl Knechtel, Aug 19 '23 at 20:01

hpaulj · Accepted Answer · 2023-08-19T20:59:05.463

This answer just makes more explicit the observations of several of the comments.

The marked duplicate isn't particularly useful, since it focuses on the common case of indexing the nth time of a list that is n items long. Here the problem is with using an intermediate indexing array that may have values that are too large.

When I run part of your code, I get:

In [2]: len(s)
Out[2]: 105
In [3]: r = []
   ...: 
   ...: for n in range(20):
   ...:  result = 1
   ...:  for k in range(n-1):
   ...:      result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
   ...:  r.append(result)
   ...: 
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[3], line 6
      4 result = 1
      5 for k in range(n-1):
----> 6     result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
      7 r.append(result)

and the ipython display highlights the r[s[n - k - 1]] expression.

Lets try it again with some prints:

In [5]: r = []
   ...: for n in range(20):
   ...:  result = 1
   ...:  for k in range(n-1):
   ...:      print(n,k, len(r), len(s),n-k-1)
   ...:      print(r[s[n - k - 1]])
   ...:      result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
   ...:  r.append(result)
   ...:  print(n,r)
   ...: 
0 [1]
1 [1, 1]
2 0 2 105 1
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[5], line 6
      4 for k in range(n-1):
      5     print(n,k, len(r), len(s),n-k-1)
----> 6     print(r[s[n - k - 1]])
      7     result += (scipy.special.binom(n - 1, k) % 2) * r[s[n - k - 1]]
      8 r.append(result)

IndexError: list index out of range

So after a couple of loops, n=2, r has 2 terms.

n-k-1 is 2-0-1=1. s[1] is 2. r[2] raises the error. I don't know why you are selecting elements of s as indices for the r. r starts empty, and grows with each append. But the values of s are not linked, in any obvious way, to the size of r. They range from 1 to 7 in a seemingly random way.

A tweak like r[s[n - k - 1]-1] solve things for this n, but what about a later s?

Trying it, it does run through to n=19, with the resulting r:

19 [1, 1, 2.0, 2.0, 5.0, 2.0, 4.0, 4.0, 10.0, 2.0, 4.0, 4.0, 10.0, 4.0, 8.0, 8.0, 23.0, 2.0, 4.0, 4.0]

Again this depends on the values of s. With the added -1, the r indexing ranges from [0,6]. So if the 6 isn't too early in the loop, it runs. But without knowing anything about s, this fix looks like a kludge.

Common List Index Out Of Range Issue, Why?

1 Answers1