I want to get a composition of a number with zeros and restrictions, i.e. Initially there is a list with restrictions on the maximum, for example [5,3,4] will mean that the composition must have at least 3 numbers (zeros are possible), and that the first cannot be more than 5 and the second cannot be more than 3, the third is more than 4 . And given the number 8 which, respectively, according to these rules must be decomposed. Tell me where similar examples of algorithms can be found or how it can be implemented.

  • What the algorithm here? First, for checking, you add up the upper bounds, if they are less than a number - a bummer. Otherwise, you stupidly think how much is superfluous, and you begin to take away (yes, in order). If the remainder is greater than the next border number, subtract as much as we can (to zero) and proceed to the next. Following the example. 5 + 3 + 4 = 12> 8, fine. Excess 12-8 = 4. Subtract from the first these 4, and we get the composition {1,3,4}. - Akina

1 answer 1

Recursively we pass through each level, limiting the following components:

 def compo(n, limits, res): if len(limits) == 0: if n == 0: print(res) return for i in range(limits[0] + 1): compo(n - i, limits[1:], res + str(i) + " ") compo(8, [5,3,4], "") 1 3 4 2 2 4 2 3 3 3 1 4 3 2 3 3 3 2 4 0 4 4 1 3 4 2 2 4 3 1 5 0 3 5 1 2 5 2 1 5 3 0
  • rather than tell me whether it is possible to transfer such a scheme to the list of lists, i.e. at the exit get a list of lists. Those. something like this (only this one works incorrectly): fulllst = [] per1 = [3, 3, 4, 2, 1] z = 5 xlst = [0] * z def col (n, point): global xlst if point == 4: if n == 0: fulllst.append (xlst) xlst = [0] * z return for i in range (per1 [point] +1): xlst [point + 1] = i col (n - i, point + 1) col (z, 0) print (fulllst) - hitandfun
  • one
    Instead of strings get lists? Yes, it is possible, but how to do it in the best way - prompted by specialists in Python. Before the recursive call, I would add the element i to the list, delete it after the call, and if you need to use this list of lists somehow, I did deepcopy instead of print (or just [c for c in res_list]) - MBo