algorithm
Algoritmo de partición entero

Información básica del algoritmo de partición entero

La partición de un entero es una forma de escribirlo como una suma de enteros positivos. Por ejemplo, las particiones del número 5 son:

• 5
• 4 + 1
• 3 + 2
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

Tenga en cuenta que cambiar el orden de los sumandos no creará una partición diferente.

La función de partición es intrínsecamente recursiva ya que los resultados de números más pequeños aparecen como componentes en el resultado de un número más grande. Sea p (n, m) el número de particiones de n que usan solo números enteros positivos que son menores o iguales que m . Se puede ver que p (n) = p (n, n) , y también p (n, m) = p (n, n) = p (n) para m > n .

Ejemplo de algoritmo de partición entero:

Espacio auxiliar: O(n^2)
Complejidad de tiempo: O(n(logn))

Implementación del algoritmo de partición Interger en C #

 public class IntegerPartition
{
    public static int[,] Result = new int[100,100];

    private static int Partition(int targetNumber, int largestNumber)
    {
        for (int i = 1; i <= targetNumber; i++)
        {
            for (int j = 1; j <= largestNumber; j++)
            {
                if (i - j < 0)
                {
                    Result[i, j] = Result[i, j - 1];
                    continue;
                }
                Result[i, j] = Result[i, j - 1] + Result[i - j, j];
            }
        }
        return Result[targetNumber, largestNumber];
    }

    public static int Main(int number, int target)
    {
        int i;
        for (i = 0; i <= number; i++)
        {
            Result[i, 0] = 0;
        }
        for (i = 1; i <= target; i++)
        {
            Result[0, i] = 1;
        }
        return Partition(number, target);
    }
}