algorithm
Geheel partitie algoritme

Basisinformatie van algoritme voor gehele partities

De partitie van een geheel getal is een manier om het te schrijven als een som van positieve gehele getallen. De partities van het getal 5 zijn bijvoorbeeld:

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

Merk op dat het wijzigen van de volgorde van de summands geen andere partitie zal creëren.

De partitiefunctie is inherent recursief van aard, omdat de resultaten van kleinere getallen als componenten verschijnen in het resultaat van een groter getal. Laat p (n, m) het aantal partities van n zijn met alleen positieve gehele getallen die kleiner zijn dan of gelijk zijn aan m . Men kan zien dat p (n) = p (n, n) , en ook p (n, m) = p (n, n) = p (n) voor m > n .

Voorbeeld van algoritme voor gehele partities:

Hulpruimte: O(n^2)
Tijdcomplexiteit: O(n(logn))

Implementatie van Interger-partitie-algoritme in 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);
    }
}