C# Zahlenproblematik

[holy]

Such dir eine aus. Deine Lösung berechnet 2724 mögliche Partitionen, das sind so ca. 37000 zu wenig (wenn die Reihenfolde nicht beachtet wird, ansonsten 380mio )

 

[maxwell-cs]

beispielsweise 9 9 9 4 0 0 0 0 0 0 fehlt. du musst b, c, d usw mit 0 statt der ziffer vorher initialisieren.
eine lösung mit einer variable für jede ziffer ist aber sowieso eher zu vermeiden, das geht mit flexibler länge deutlich eleganter.

 

[efcoyote]

Die angesprochenen 37338 beziehen sich auf die Zerlegung von 40 ohne Ziffernbeschränkung. In diesem Fall beträgt die Beschränkung aber 10 Ziffern. Außerdem beachte ich die Reihenfolge nicht. Alle zu 10 fehlenden Ziffern sind bei meiner Lösung mit 0 aufzufüllen. Die könnte man ziemlich simpel einfach in die Ausgabe schreiben.

9 9 9 9 4 0 0 0 0 0 fehlt nicht und wird bei mir als 4 9 9 9 9 ausgegeben.
Die Initialisierung mit 1 ist richtig, da Nullen nicht mit ausgegeben werden. Das beschleunigt die Iteration.

 

[efcoyote]

Der Vollständigkeit halber noch die kurze Lösung für beliebige Zahlen

    private static void Main(String[] args)
    {
      StringBuilder sb = new StringBuilder();
      GetPartialNumbers(40, 9, 10, sb);
      File.WriteAllText("numbers.txt", sb.ToString());
      System.Console.ReadLine();
    }

    private static void GetPartialNumbers(Int32 numberToPart, Int32 maxNumberPerPart, Int32 maxParts, StringBuilder sb, params Int32[] partialNumbers)
    {
      Int32 sum = partialNumbers.Sum();
      if (numberToPart - sum > 0)
      {
        if (partialNumbers.Count() < maxParts)
        {
          Int32 lastPartialNumber = (partialNumbers.Any() ? partialNumbers.Last() : 1);
          for (Int32 i = lastPartialNumber; i <= Math.Min(numberToPart - sum, maxNumberPerPart); i++)
          {
            var newPartialNumbers = new List<Int32>(partialNumbers.ToList());
            newPartialNumbers.Add(i);
            GetPartialNumbers(numberToPart, maxNumberPerPart, Math.Min(maxParts, numberToPart), sb, newPartialNumbers.ToArray());
          }
        }
      }
      else
      {
        String line = String.Join(" ", partialNumbers);
        System.Console.WriteLine(line);
        sb.AppendLine(line);
      }
    }

Man übergibt die Zahl die zu teilen ist, die maximale Größe eines Teils sowie die maximale Anzahl an Teilen. Die Parameter für den ursprünglichen Post wären demnach 40, 9 und 10. Ausgegeben werden nur die Partitionierungen nicht die Kombinationen, d.h. die Reihenfolge wird nicht beachtet.

GetPartialNumbers(40, 9, 10, sb) = 2724
GetPartialNumbers(40, 40, 40, sb) = 37338