algorithm
Integer-Partitionsalgorithmus

Grundlegende Informationen zum Integer-Partitionsalgorithmus

Die Partition einer Ganzzahl ist eine Möglichkeit, sie als Summe positiver Ganzzahlen zu schreiben. Zum Beispiel sind die Partitionen der Zahl 5:

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

Beachten Sie, dass durch das Ändern der Reihenfolge der Summanden keine andere Partition erstellt wird.

Die Partitionsfunktion ist von Natur aus rekursiv, da die Ergebnisse kleinerer Zahlen als Komponenten im Ergebnis einer größeren Anzahl erscheinen. Sei p (n, m) die Anzahl der Partitionen von n, wobei nur positive ganze Zahlen verwendet werden, die kleiner oder gleich m sind . Man kann sehen, dass p (n) = p (n, n) und auch p (n, m) = p (n, n) = p (n) für m > n ist .

Beispiel eines Integer-Partitionsalgorithmus:

Hilfsraum: O(n^2)
Zeitkomplexität: O(n(logn))

Implementierung des Interger-Partitionsalgorithmus 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);
    }
}