Formel für alle Teilzahlen, die in Summe eine andere Zahl ergeben?

Du kannst Dir schonmal die innerste Schleife sparen. Drei verschachtelte Schleifen reichen aus, weil sich der vierte Wert dann automatisch aus der Randbedingunge (Summe = 100) ergibt.
Außerdem kannst Du die äußeren Schleifen optimieren. Beispiel: i+e > 100. Dann kannst Du die weitere Prüfung abbrechen.

pumuckl

Brauchst du Permutationen? D.h. ist 1,1,1,97 das Selbe wie 1,1,97,1 oder müssen beide Zahlenfolgen gesondert ausgegeben werden? Falls eine geordnete Folge (z.B. kleinere Zalen zuerst) ausreichend ist, dann kannst du dir überlegen, dass die Schleifen andere Randbedingungen haben können.

Jester

Mußt du die wirklich alle erzeugen? Oder ist die Aufgabe nur zu sagen wieviele es sind?

Helfer in der Not schrieb:

Stihwort Partitionsfunktion und ergezigende Funktionen

Danke! Scheint genau mein Problem zu beschreiben.

Trollolololoo schrieb:

Du kannst Dir schonmal die innerste Schleife sparen. Drei verschachtelte Schleifen reichen aus, weil sich der vierte Wert dann automatisch aus der Randbedingunge (Summe = 100) ergibt.
Außerdem kannst Du die äußeren Schleifen optimieren. Beispiel: i+e > 100. Dann kannst Du die weitere Prüfung abbrechen.

Danke für den Tipp!

pumuckl schrieb:

Brauchst du Permutationen? D.h. ist 1,1,1,97 das Selbe wie 1,1,97,1 oder müssen beide Zahlenfolgen gesondert ausgegeben werden?

Permutationen benötige ich nicht. D.h. für mich ist es ausreichend, wenn ich einmal die Folge von zb 1+1+1+97 habe, egal in welcher Reihenfolge.

Jester schrieb:

Mußt du die wirklich alle erzeugen? Oder ist die Aufgabe nur zu sagen wieviele es sind?

Ich muss sie tatsächlich erzeugen, da ich sie dann weiter verwenden möchte (deshalb muss ich sie dann auch noch geeignet zwischenspeichern). Der geplante Wertebereich liegt zwischen 1-4 Byte.

pumuckl

So in etwa:

#include <vector>

void print(std::vector<unsigned> const& sequence);

void partitionSum(std::vector<unsigned>& sequence, unsigned count, unsigned rest, unsigned min =1)
{
  assert(count > 0);
  if (count == 1)
  {
    sequence.push_back(rest);
    print(sequence);
    sequence.pop_back();
    return;
  }

  for (unsigned i = min; i <= rest/count; ++i)
  {
    sequence.push_back(i);
    partitionSum(sequence, count-1, rest-i, i);
    sequence.pop_back();
  }
}

Aufruf kannste dir ja denken

Danke pumuckl!

Gibt es dafür auch eine implementierung in c?

Ralph_ schrieb:

Ich muss sie tatsächlich erzeugen, da ich sie dann weiter verwenden möchte (deshalb muss ich sie dann auch noch geeignet zwischenspeichern). Der geplante Wertebereich liegt zwischen 1-4 Byte.

bist du dir sicher, dass du das willst? Schau dir mal an, wie viele Zahlen das sind. Wir lösen das mal schrittwise:

Sei N die Zeilsumme (in deiner Frage N=100) und K_k(N) die Anzahl der Kombinationen mit k Zahlen auf N aufzusummieren.

für k=2 ohne Permuationen ist dies einfach:
K_2(N) = N-1
Für K = 3 kann man das berechnen indem man einfach eine Zahl k wählt und dann die Anzahl der Kombinationen der restlichen N-k Zahlen angibt:
K_3(N) = N-1 K_2(N-1) = \sum_{k=1}^{N-1} K_2(N-k)
= \sum_{k=1}^{N-1} N-k-1 =N^2/2 -...

und K_4(N) = \sum_{k=1}^{N-1} K_3(N-k)

das kannst du dir selbst ausrechnen, aber du kommst darauf, dass K_4(N) ein Polynom der Ordnung 3 in N ist.

Nun sagst du, dass dein Wertbereich 1-4 Bytes = 32 Bits ist. Das heißt du kannst K_3(N) mit der Anzahl der bits b abschätzen durch 2^(3b)
für b = 10 (also =1024) erhälst du also schon irgendwas um 2^30 Kombinationen, und 16 Bit sollten dir schon lange deinen Speicher sprengen. An deiner Stelle würde ich mir eine andere Lösungsstrategie suchen.

Sorry, das war mit Permutationen

@pumuckl: Deine Lösung scheint gut zu funktionieren, Danke nochmals!

@jkio2: Ich versuche gerade das ganze in C zu realisieren. Falls jemand mehr Erfahrung in C hat, würde ich mich über Hilfe freuen.

@otze_logout: Ja, beim Testen habe ich bereits festgestellt, dass es mit dem Speicher etwas knapp wird. Der Wertebereich von einem Byte würde mir demnach wohl auch reichen (0-255).