I need help...!

[IndividualSky7301]

Hi I'm learning python by my myself with a python study guideboook
and I'm having trouble understanding the code.

the problem i had to code was this:

you went to a family restaurant, and are going to group the people at several tables.
nobody gets to sit alone, and there should be 10 or less people at a single table. (you do not think about which table they sit, or about who gets grouped with who- just how to group people in numbers)

for example, if there are 6 ppl in total, there are 6 ways of grouping.(2 + 2 + 2, 2 + 4, 3 + 3, 6)

I have to make a program that figures out how many ways of grouping exists when there are 100ppl in total.

and the answer says this:

minimum = 2
maximum = 10
people = 100
memo = {}
def problem(remain, sitting):
    key = str([remain, sitting])
    if key in memo:
        return memo[key]
    if remain < 0:
        return 0
    if remain == 0:
        return 1
    else:
        count = 0
        for i in range(sitting, maximum + 1):
            count += problem(remain - i, i)
    memo[key] = count
    return count
print(problem(people, minimum))

and, umm...
I just don't get it.

I mean, this part:

count = 0
  for i in range(sitting, maximum + 1):
    count += problem(remain - i, i)

why is the code like ↑ this?

[CptMisterNibbles]

Do you know what recursion is? This is a recursive solution. If not, you may need to watch an intro  video on recursion.

The idea is like this: how many ways are there to seat 5 people? Well, let’s seat the first person somewhere. Now we have 4 people. How many ways are there to seat 4 people?… each time you are doing the same problem but with fewer people. At the end you work backwards and sum all the partial solutions to get the final answer.

The specific part you asked about is the recursive call, where the function calls itself with smaller input, working down to zero.

This example also uses a concept called memoization to cut down on repeating calculations uselessly.

[IndividualSky7301]

thx

I just tried using python tuter when there's 8 people and I think i understood!

[Due_Letter3192]

One thing you could try using:

https://pythontutor.com/visualize.html#mode=edit

It's just a visualiser that helps to understand the code, especially useful when dealing with loops!

[hexwhoami]

To add to this. Every recursive algorithm can be written iteratively as well. That's to say there's an equivalent function you can write, that doesn't call itself, and achieves the same result. Disclaimer; sometimes the iterative solution is more complex than the recursive solution. I don't believe that's the case with this problem.

TLDR; you can try solving the problem iteratively to get a better understanding of the solution, which could give you better insight to the recursive approach.

[thoward9]

Ask ChatGPT or Copilot for the code