What's the difference between these two pieces of code?

Question

I'm currently looking at this answer on Stackoverflow about finding combinations of k elements given an n long string. However while making some changes to it (to learn more about it, adapt it to my needs, and convert it to c), I found some problems.

Taking this piece of code:

def comb(sofar, rest, k):
  if k == 0:
    print(sofar)
  else:
    for i in range(len(rest)):
       comb(sofar + rest[i], rest[i+1:], k-1)

and adding a variable "n" which is supposed to keep the length of the string:

def comb(sofar, rest, n, k):
  if k == 0:
    print(sofar)
  else:
    for i in range(0, n):
       comb(sofar + rest[i], rest[i+1:], n-1, k-1)

Technically shouldn't these do the same thing? I'm getting a "string index out of range error" but should len(rest) be the same as "n"?

edit:

comb is called with:

comb("", "12345", 3)

comb2 is called with:

comb("", "12345", 5, 3)

How are you sending `n`? It is not the same by the way. Because value of `n` and the `len(rest)` need not be same. — psiyumm, Nov 15 '15 at 06:57
why would they not be the same though? each time i call comb, i remove the first letter and so subtract 1 from n accordingly right? and I added how I call the function as an edit — projectdelphai, Nov 15 '15 at 07:00
No the lengths are not matching, just manually try to iterate over the loop and you will find your error. I think it should be `n - i - 1` rather than `n - 1` — psiyumm, Nov 15 '15 at 07:01
ohhhhh, cause it's rest[i+1:] so it cuts it short but a smaller amount for each iteration through the loop, that makes sense. Thanks a lot! If you put that as an answer, I'd be glad to accept it! Thanks again :P — projectdelphai, Nov 15 '15 at 07:04
lol sorry, apparently there's a 3 minute waiting period and I got distracted while waiting for it :P — projectdelphai, Nov 16 '15 at 09:33

score 3 · Answer 1 · answered Nov 15 '15 at 07:01

3

You call comb( ..., rest[i+1:], n-1, ...) and rest[i+1:] can be shorter then n-1

answered Nov 15 '15 at 07:01

furas

134,197
12
106
148

score 2 · Accepted Answer · answered Nov 15 '15 at 07:06

So here is the problem in your code:

comb(sofar + rest[i], rest[i+1:], n-1, k-1)

Your tail recursive call is not correct. You are using rest[i+1:] and it's length is not n - 1 for two reasons. You are not updating n and you are not modifying rest in place. So length of rest will always be less than n - 1 for all i > 0.

You should replace it by n - i - 1.

NOTE: The first method is the correct way to do anyways. Minimize your dependencies.

What's the difference between these two pieces of code?

2 Answers2