Alle Zahlen mit gleicher Quersumme auflisten

Hallo Forum,

wie würde man alle Zahlen mit gleicher Quersumme in einem beliebigen Zahlensystem auflisten. Ich benötigen den Algo um n Dinge auf m Behälter zu verteilen. n und m sind variabel. Meistens gibt es 20 Dinge und 10 Behälter.

Kleines Beispiel: Es sollen 7 Dinge auf 4 Behälter verteilt werden.

Das Ergebnis soll so aussehen:
0007
0016
0025
...
0070
0106
0115
...
7000
Jede Stelle steht für einen Behälter, die Ziffer für die Befüllung.

- Die Quersumme ist immer die Anzahl der Dinge.
- Das Zahlensystem ist #Dinge+1.
- Wenn auf eine Ziffer ein 1 drauf kommt wird (#Dinge+1)^(Stelle-1) gerechnet. Im Gegenzug wird nach dem gleichen Muster woanders ein 1 abgezogen. Allerdings kann es vorkommen das mehrere 1 verschoben werden. Siehe diesen Übergang:
0610
1006

Ich habe mal ein Excel Makro geschrieben um ein Muster zu erkennen:

Public Sub start()
   Call LoopArray(7, 4)
End Sub

Private Sub LoopArray(items As Long, container As Long)
   Dim CurrentDistribution() As Long
   Dim rest As Long, i As Long, QSum As Long, lActualRow As Long
   Dim counter As Currency

   ReDim CurrentDistribution(1 To container) ' Hier speichern wir die momentane Zerlegung ab:
   ' Es werden alle Zerlegungen durchgegangen. Auch die ohne passende Quersumme:
   For counter = 0 To (items + 1) ^ (container + 1)

      ' Jetzt zerlegen wir den Counter im momentanen Zahlensystem:
      rest = counter: QSum = 0
      For i = 1 To container
         CurrentDistribution(i) = rest Mod (items + 1)
         QSum = QSum + CurrentDistribution(i)
         rest = rest \ (items + 1)
      Next i

      ' Hat die momentane Zerlegung die richtige Quersumme? Wenn ja rausschreiben.
      If QSum = items Then
         lActualRow = lActualRow + 1
         For i = 1 To container
            Tabelle1.Cells(lActualRow, container + 1 - i) = CurrentDistribution(i)
         Next i
      End If
   Next counter
End Sub

Ich finde aber keine Lösung.

In diesem Minibeispiel kann die Lücke zwischen zwei Zahlen mit der richtigen Quersumme schon 3584 betragen. Es wird also unsinnigerweise 3583 mal die Schleife durchgegangen und die Quersumme errechnet. Ein Aufruf wie "LoopArray(20, 10)" sprengt aber schon meine Lebenserwartung.

Wie kann ich die Sache beschleunigen? Ich könnte jetzt stattdessen mit einer extra Funktion die Einsen von links nach rechts verschieben. (Das kann ich selber machen) Aber vielleicht gibt es dafür irgendeine mathematische Formel?

Vielen Dank

Argh: Schon der erste Fehler.

- Wenn auf eine Ziffer ein 1 drauf kommt wird (#Dinge+1)^(Stelle-1) gerechnet. Im Gegenzug wird nach dem gleichen Muster woanders ein 1 abgezogen. Allerdings kann es vorkommen das mehrere 1 verschoben werden. Siehe diesen Übergang:
0610
1006

Der Übergang ist natürlich:
0700
1006

Bashar

Der Fehler liegt schon darin, dass du "n Dinge in m Behältern" als Zahl mit m Stellen in einem Ziffernsystem zur Basis n darstellen willst. Ansonsten ist die richtige Lösung nicht, alle Kombinationen durchgehen und die gewünschten zu behalten, sondern gleich nur die gewünschten zu generieren. So nach dem Motto: Pack 1 Teil in den ersten Behälter. Wieviel hab ich noch? Ermittle alle Möglichkeiten, sie auf den Rest zu verteilen. Dann pack 2 Teile in den ersten Behälter, mach das gleiche usw.

CStoll

Du könntest rekursiv die Gesamtzahl in alle möglichen Summen zerlegen:

void zerlege(zahl,länge)
{
  static vector<int> summanden;
  if(summanden.size())==länge)
  {
    ausgabe();
    return;
  }
  for(i=0;i<=zahl;++i)
  {
    summanden.push_back(i);
    zerlege(zahl-i,länge);
    summanden.pop_back();
  }
}

@edit @Bashar: Und da haben wir schon den Ausgleich

Wenn ich es richtig sehe hattet Ihr beide die richtige Idee. Jetzt muß ich nicht in irgendwelchen Arrays rumprokeln.... vielen vielen Dank Bashar und CStoll

Black Shadow

Sry, auch wenn Off Topic und ich Mathe-Noob: Hat man es eigentlich dem Zehnersystem zu verdanken, dass durch die Quersumme bestimmen kann, dass Zahlen durch 3 teilbar sind? würde das z.b. im hexadezimalen ähnlich gehen?
Könnte man nicht auf ähnliche weise prüfen, ob Zahlen durch andere Zahlen ohne Rest teilbar sind, wenn man sie im richtigen Zahlensystem hätte? (mist, ich glaube da hab ich mir gerade selbst die antwort gegeben , aber wenn jemand was dazu sagen will, bitte ^^ ).