Número de formas de dividir un número dado como un conjunto de enteros en orden decreciente

Dados dos números $a$ y $metro$ . La tarea es encontrar el número de formas en que a puede representarse mediante un conjunto $\{n_1, n_2, ...., n_c\}$ tal que $a >= n_1 > n_2 > ... > n_m > 0$ y la suma de estos números sea igual a a . Además $1 <= c <= m$ (el tamaño máximo del conjunto no puede exceder m ).

Ejemplos :

Entrada : a = 4, m = 4
Salida : 2 –> ({4}, {3, 1})
Nota : {2, 2} no es un conjunto válido ya que los valores no están en orden decreciente

Entrada : a = 7, m = 5
Salida : 5 –> ({7}, {6, 1}, {5, 2}, {4, 3}, {4, 2, 1})

Enfoque: este problema se puede resolver mediante Divide and Conquer utilizando un enfoque recursivo que sigue las siguientes condiciones:

Si a es igual a cero, se ha encontrado una solución.
Si a > 0 y m == 0, este conjunto viola la condición ya que no se pueden agregar más valores en el conjunto.
Si ya se ha realizado el cálculo para los valores dados de a , m y prev (último valor incluido en el conjunto actual), devuelva ese valor.
Inicie un bucle desde i = a hasta 0 y si i < anterior , cuente el número de soluciones si incluimos i en el conjunto actual y lo devolvemos.

A continuación se muestra la implementación del enfoque anterior:

# Python3 code to calculate the number of ways 
# in which a given number can be represented 
# as set of finite numbers
  
# Import function to initialize the dictionary
from collections import defaultdict
  
# Initialize dictionary which is used 
# to check if given solution is already 
# visited or not to avoid
# calculating it again
visited = defaultdict(lambda : False)
  
# Initialize dictionary which is used to
# store the number of ways in which solution
# can be obtained for given values
numWays = defaultdict(lambda : 0)
  
# This function returns the total number
# of sets which satisfy given criteria
# a --> number to be divided into sets
# m --> maximum possible size of the set
# x --> previously selected value
def countNumOfWays(a, m, prev):
      
    # number is divided properly and
    # hence solution is obtained
    if a == 0:
        return 1
      
    # Solution can't be obtained
    elif a > 0 and m == 0:
        return 0
      
    # Return the solution if it has
    # already been calculated
    elif visited[(a, m, prev)] == True:
        return numWays[(a, m, prev)]
      
    else:
        visited[(a, m, prev)] = True
  
        for i in range(a, -1, -1):
            # Continue only if current value is 
            # smaller compared to previous value
            if i < prev:
                numWays[(a,m,prev)] += countNumOfWays(a-i,m-1,i)
  
        return numWays[(a, m, prev)]
  
# Values of 'a' and 'm' for which
# solution is to be found
# MAX_CONST is extremely large value 
# used for first comparison in the function
a, m, MAX_CONST = 7, 5, 10**5
print(countNumOfWays(a, m, MAX_CONST))

Producción:

Complejidad del tiempo: O(a*log(a))

Publicación traducida automáticamente

Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta