Python How does a non one way recursive function return all results

Recursion (recursion) is a magical programming technique that greatly simplifies code and makes it look more concise. However, recursive design is very abstract and not easy to master. Often, we think from the top down, recursion from the bottom up--that's why recursion doesn't seem intuitive enough.

Among the concepts related to recursion, linear recursion/nonlinear recursion and one-way recursion/non-one-way recursion are very important. If you want to master recursion technology, you must have a deep understanding. On the basic concept of recursion, interested readers can refer to my blog "Python Recursive Algorithm Reference". Today, we only talk about how non-one-way recursive functions return all results for knapsack problem.

Behind the knapsack problem is one of the seven mathematical problems in the world, the uncertain problem of polynomial complexity. As a programmer, this problem can be roughly understood as a combinatorial optimization problem. The knapsack problem is usually described as follows: given a group of items, each item has its own weight and price. Within the limited total weight, how to choose can make the total price of the item the highest. If different restrictions and conditions are added, many variants of knapsack problem can be derived. For example, the following problem seems to be far from the knapsack problem, but it is still a typical knapsack problem in essence.

In a hero battle game, the player has m pieces of equipment and n heroes. He can assign 0 or more pieces of equipment to each hero, and different heroes will get different attack power when they have different numbers of equipment. How does the player allocate this m piece of equipment, which can make the n hero gain the maximum attack power? Take the player with 5 pieces of equipment and 3 heroes as an example. The following table has 3 rows and 6 columns, which correspond to the attack power of 3 heroes with 0 to 5 pieces of equipment respectively.

	0件	1件	2件	3件	4件	5件
英雄1	0	1	3	5	7	9
英雄2	0	1	1	3	3	7
英雄3	0	3	4	5	6	7

Even if you are not familiar with the knapsack problem, it is not difficult to find a solution:

Find out all possible equipment distribution schemes Calculate the attack value for every 1 scheme Choose the allocation scheme with the largest attack value

1. Find out all possible equipment distribution schemes

Finding out all the solutions to assign m pieces of equipment to n heroes is the core of solving the problem. Here, circular nesting is not feasible, because the number of nesting levels is an input variable. Recursion is the feasible method I think of.

>>> def bag(m, n, series=list()):
    if n == 1:
      for i in range(m+1):
        print(series+[i])
    else:
      for i in range(m+1):
        bag(m-i, n-1, series+[i])
  
>>> bag(3,2) #  Will 3 Parts of equipment are assigned to 2 All the plans of a hero 
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[3, 0]

The recursive function bag prints out the whole scheme of assigning 3 pieces of equipment to 2 heroes. Obviously, this is not a one-way recursion, because there are multiple recursive calls at the same level 1, which means that the recursive process has multiple exits from the recursive exit. For non-one-way recursion, return cannot be used to return results. So, how do recursive functions return all solutions? Please look at the following example.

>>> def bag(m, n, result, series=list()):
 if n == 1:
 for i in range(m+1):
  result.append(series+[i])
  #print(result[-1])
 else:
 for i in range(m+1):
  bag(m-i, n-1, result, series+[i])

  
>>> result = list()
>>> bag(5, 3, result) #  Will 5 Parts of equipment are assigned to 3 A hero, shared 56 Species allocation scheme 
>>> len(result)
56
>>> result
[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 0, 4], [0, 0, 5], 
[0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 0], 
[0, 2, 1], [0, 2, 2], [0, 2, 3], [0, 3, 0], [0, 3, 1], [0, 3, 2], 
[0, 4, 0], [0, 4, 1], [0, 5, 0], [1, 0, 0], [1, 0, 1], [1, 0, 2], 
[1, 0, 3], [1, 0, 4], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3], 
[1, 2, 0], [1, 2, 1], [1, 2, 2], [1, 3, 0], [1, 3, 1], [1, 4, 0], 
[2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3], [2, 1, 0], [2, 1, 1], 
[2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 3, 0], [3, 0, 0], [3, 0, 1], 
[3, 0, 2], [3, 1, 0], [3, 1, 1], [3, 2, 0], [4, 0, 0], [4, 0, 1], 
[4, 1, 0], [5, 0, 0]]

In the above code, before calling the recursive function, a global list object result is created and passed to the recursive function as an argument. After the recursive call, the entire equipment allocation scheme is stored in the list object result.

2. Calculate the attack value for every 1 scenario

Traverse 56 allocation schemes, calculate the sum of attack power of each scheme, and save it to a new list v. p gives 3 heroes attack power from 0 to 5 pieces of equipment respectively.

>>> p = [
 [0,1,3,5,7,9],
 [0,1,1,3,3,7],
 [0,3,4,5,6,7]
]
>>> v = list()
>>> for item in result:
    v.append(p[0][item[0]] + p[1][item[1]] + p[2][item[2]])
 
>>> v
[0, 3, 4, 5, 6, 7, 1, 4, 5, 6, 7, 1, 4, 5, 6, 3, 6, 7, 3,
 6, 7, 1, 4, 5, 6, 7, 2, 5, 6, 7, 2, 5, 6, 4, 7, 4, 3, 6, 
 7, 8, 4, 7, 8, 4, 7, 6, 5, 8, 9, 6, 9, 6, 7, 10, 8, 9]

3. Choose the allocation scheme with the largest attack value

Find out the serial number of the maximum value in v list, and then get the equipment allocation scheme with the greatest attack power.

>>> max(v)
10
>>> result[v.index(max(v))] 
[4, 0, 1]

The best allocation scheme is that the first hero holds 4 pieces of equipment, the second hero has no equipment, and the third hero holds 1 piece of equipment. At this time, the sum of the attack power of the three heroes is the maximum, and its value is 10.