Algorithmus zu Finden aller schwachen Kompostionen

firfan

Hall zusammen,

ich möchte ein Programm schreiben, dass alle schwache Kompositionen von n findet.

Seien n und k natürliche Zahlen. Eine Darstellung n = a_1 +
· · · + a_k mit natürlichen Zahlen a_i >= 0 heißt schwache Komposition von n mit k
Teilen. Die Reihenfolge der Summanden wird dabei beachtet.

Bsp. n=2, k=3
Dann hätte ich folgende sechs Möglichkeiten, n=2 in k=3 Teile zu unterteilen: (a_1,a_2,a_3)=

(2,0,0)
(0,2,0)
(0,0,2)
(1,1,0)
(1,0,1)
(0,1,1)

Diese Kombinationen soll mein Programm finden.

Ich lerne gerade Programmieren und bin deshalb für eure Hilfe dankbar!

Viele Grüße
firfan

CStoll

Ich würde das rekursiv per Backtracking lösen: nimm alle Zahlen 0<=i<=n und bilde die Kombination von n'=n-i mit k'=k-1 Teilen.

firfan

[quote="CStoll"]Ich würde das rekursiv per Backtracking lösen: nimm alle Zahlen 0<=i<=n und bilde die Kombination von n'=n-i mit k'=k-1 Teilen.[/quote]

Vielen Dank, CStoll, für deine Antwort!

Ich verstehe das Prinzip leider noch nicht.

i=0, dann ist n'=2-0=2 und k'=3-1=2.
Die Kombinationen, für n'=2 und k'=2 sind
(0,2), (2,0) und (1,1)

Wie geht der Algorithmus dann weiter?

CStoll

firfan schrieb:

Ich verstehe das Prinzip leider noch nicht.

i=0, dann ist n'=2-0=2 und k'=3-1=2.
Die Kombinationen, für n'=2 und k'=2 sind
(0,2), (2,0) und (1,1)

Wie geht der Algorithmus dann weiter?

Jetzt kannst du vor jede Teil-Lösung den herausgezogenen Summanden i davorschreiben und hast jeweils eine Lösung für das Gesamtproblem - in dem Beispiel (0,0,2), (0,2,0), (0,1,1). Wobei, im Endeffekt würde ich die bisherigen Summanden beim rekursiven Aufruf mit übergeben und auf der untersten Ebene (bei k=0) ausgeben oder weiterverarbeiten.

PS: Willst du eigentlich eine C++ Lösung oder allgemeine Hilfestellung zum Problem?

firfan

Ok. Das Problem ist dann, dass der herausgezogene Sumamand i nicht nur vor der Teil-Lösung platziert werden soll/kann. Es kann auch dahinter, oder zwischen der Teillösung platziert werden.

Ich brauche erstmal eine allgemeine Hilfestellung, wie der Algorithmus aussehen kann. Dann würde ich den Algorithmus implementieren. Dabei werden sicherlich noch C++ Fragen auftreten.

C++ Forumbot

Dieser Thread wurde von Moderator/in CStoll aus dem Forum C++ (auch C++0x) in das Forum Mathematik und Physik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

CStoll

firfan schrieb:

Ok. Das Problem ist dann, dass der herausgezogene Sumamand i nicht nur vor der Teil-Lösung platziert werden soll/kann. Es kann auch dahinter, oder zwischen der Teillösung platziert werden.

Nein, mußt du nicht - wenn du mit der 0 als erstem Summanden fertig bist, kommen als nächstes die Kompositionen dran, deren erster Summand 1 ist. Und dabei wirst du auch die finden, bei denen die 0 in der Mitte oder am Ende stehen wird.

firfan

Hallo CStoll,

per Nachrechnen anhand einiger Beispiele habe ich mit deiner Methode alle Kompositionen gefunden. Ich weiß aber noch nicht, wie ich den Algorithmus aufschreiben soll.

Die Funktion, die mir alle Kompostionen von n in k Teile findet, nenne ich compostion_generator(n,k). Ich kenne nur Funktionen, die einen Variablenwert zurückgeben. Die Kompositionen sind aber evtl. mehrere Vektoren. Als welchen Variabletyp sollen die Kompositionen gespeichert werden. Die Vektoren müssen ja auch erweiterbar sein.

Ich danke dir!

PS. Kennst du eine Seite mit einem Beispiel von Backtracking?

[quote="CStoll"]Nein, mußt du nicht - wenn du mit der 0 als erstem Summanden fertig bist, kommen als nächstes die Kompositionen dran, deren erster Summand 1 ist. Und dabei wirst du auch die finden, bei denen die 0 in der Mitte oder am Ende stehen wird.[/quote]

CStoll

Eine konkrete Seite kenne ich leider nicht. Aber afair muß selbst der klassische Kandidat für Backtracking (Damenproblem) eine Liste von Lösungen herausgeben. In C++ würde ich als zusätzlichen Parameter einen verschachtelten vector<> übergeben, in den ganz unten die gefundenen Kompositionen geschrieben werden (oder eine Funktion/Funktor, die einen vector<int> entgegennimmt und verarbeiten soll).

cooky451

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

bool perm_next(std::vector<int>& v, int n)
{
  if (v.back() >= n)
    return false;
  for (std::vector<int>::iterator i = v.begin(); i < v.end() - 1; ++i)
  {
    if (*i)
    {
      if (*i < n)
      {
        --*i;
        ++*(i + 1);
      }
      else
      {
        *i = 0;
        *v.begin() = n - 1;
        ++*(i + 1);
      }
      break;
    }
  }
  return true;
}

int main()
{
  const int n = 2;
  std::vector<int> v(4);
  v[0] = n;

  do {
    for (std::vector<int>::iterator i = v.begin(); i < v.end(); ++i)
      std::cout << *i << " ";
    std::cout << std::endl;
  } while (perm_next(v, n));
}

(Hoffentlich kommen da jetzt nicht irgendwann falsche Ergebnisse und ich blamiere mich völlig. )

Edit:
Header angegeben.

Wie erwartet funktioniert das leider nicht korret.. na ja, vielleicht hilft dir ja der Ansatz.

firfan

@CStoll: Vielen Dank! Ich habe das Backtracking verstanden.

@cooky451 : Vielen Dank! Ich habe versucht, den Code zu verstehen. Leider erfolglos. Ich habe getestet für n=2, und k= 3, da ist der Output richtig.

Für n=4, und k =3 fehlen drei Kompositionen.
Der Output ist:
4 0 0
3 1 0
2 2 0
1 3 0
0 4 0
3 0 1
2 1 1
1 2 1
0 3 1
0 2 2
0 1 3
0 0 4

Es fehlen (2,0,2), (1,1,2) und (1,03).

Könntest du mir bitte die Idee hinter dem Code erklären? Danke!

cooky451

firfan schrieb:

Könntest du mir bitte die Idee hinter dem Code erklären? Danke!

Da der Code ja leider nicht wirklich funktioniert, werde ich mal lieber nicht auf Einzelheiten eingehen.
Die Grundidee ist es, sich eine art Permutationsregel zu überlegen, die für jeden Vektor genau einen Folgevektor definiert. Wenn man es schafft, eine solche Regel aufzustellen die sicher alle Kombinationen abdeckt hat man schon gewonnen.
Ich bin mir aber nicht sicher, ob das hier klappt. Ich setze mich noch mal drann, wenn ich eine (immer funktionierende) Regel finde melde ich mich wieder.

Edit:
Die einfachste nicht funktionierende Kombination dürfte sein: k = 3, n = 3.
Es fehlt die Permutation (1, 0, 2). Die Regel von (0..., n, ...) ist also falsch. // Edit: War nicht falsch, ich hatte einfach nur ein if() zu viel.

firfan

Vielen Dank, cooky451! Die Anzahl der Kompositionen von n in k Teile ist:

$\binom{n+k-1}{k-1} = \binom{n+k-1}{n}$

Also (n+k-1) über (k-1) bzw. (n+k-1) über n.

Damit kann überprüft werden, ob die Anzahl der Output-lösungen stimmen.

Übrigens, weißt du, warum meine Latex-Darstellung nicht funktionert? Das Problem hatte ich auch beim Zitieren.

CStoll

firfan schrieb:

Übrigens, weißt du, warum meine Latex-Darstellung nicht funktionert? Das Problem hatte ich auch beim Zitieren.

Das liegt an dem System, mit dem die Latex-Codes hier verarbeitet wird - afaik wird daran bereits gearbeitet.

cooky451

Probier mal

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

bool perm_next(std::vector<int>& v, int n)
{
  if (v.back() >= n)
    return false;
  for (std::vector<int>::iterator i = v.begin(); i < v.end() - 1; ++i)
  {
    if (*i)
    {
      int tmp = *i;
      *i = 0;
      *v.begin() = tmp - 1;
      ++*(i + 1);
      break;
    }
  }
  return true;
}

int main()
{
  int n;
  std::vector<int> v;

  while (1)
  {
    v.clear();
    std::cout << "k: ";
    std::cin >> n;
    v.resize(n);
    std::cout << "n: ";
    std::cin >> n;
    v[0] = n;

    int count = 0;

    do {
      for (std::vector<int>::iterator i = v.begin(); i < v.end(); ++i)
        std::cout << *i << " ";
      std::cout << std::endl;
      ++count;
    } while (perm_next(v, n));

    std::cout << "count: " << count << std::endl;
    std::cout << "----------" << std::endl;
  }
}

Ich hatte meine eigene Regel nicht befolgt.

Edit:
Ganzes Programm eingefügt.

firfan

Ok danke, CStoll! Ich bin Neuling hier und dachte, ich hätte was nicht richtig eingestellt.

cooky451

@TE
Funktionierts?

PS:
Könnte mir mal einer erklären was "x über y" heißt, oder einen Wikipedia Link liefern? Ich lese das jetzt schon zum wiederholten Male, aber kann mir keinen Reim darauf machen. Oo

CStoll

cooky451 schrieb:

Könnte mir mal einer erklären was "x über y" heißt, oder einen Wikipedia Link liefern?

Mache ich doch gerne: Die offizielle Bezeichnung für das Konstrukt nennt sich Binomialkoeffizient.

firfan

Sorry, das Testen hat lange gedauert.
Also ich habe mal für k=5 und n=30 getestet. Nach meiner Rechung sind es 46.376 Kompositionen. Das macht der Code auch. Prima!

Seit einer halben Stunde teste ich für k=5 und n=100. Nach meiner Rechnung ist das fast das 100-fache wie oben. Also 4.598.126 Kompositionen. Ich hoffe und glaube, dass das funktioniert.

Dann kannst du ja jetzt die Idee deines Codes erklären.

cooky451

CStoll schrieb:

Binomialkoeffizient.

Ah! Super, danke.

firfan schrieb:

Seit einer halben Stunde teste ich für k=5 und n=100. Nach meiner Rechnung ist das fast das 100-fache wie oben. Also 4.598.126 Kompositionen. Ich hoffe und glaube, dass das funktioniert.

LOL. Das läuft bei mir in unter 1 ms durch. Das Ergebnis ist 4.598.126. Vielleicht solltest du einfach mal die Ausgabe lassen, siehe Code oben, einfach die Zeilen 41, 42, 43 auskommentieren.

Die Idee war, dass sich das eigentlich nicht groß vom üblichen "Zählen" unterscheiden dürfte. Im 3er System würde man ja z.B. so zählen:

0
1
2 // "Überlauf"
10
11
..

Wenn man jetzt jede Ziffer als Teil eines Vektors, welcher die ganze Zahl darstellt ansieht: (Im Code ist das dann genau umgekehrt, da sonst v[0] die letzte und nicht die erste Ziffer wäre.)
für k = 3:
(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 1, 0)
(0, 1, 1)
..

Soweit das Grundgerüst, so kann man sich durch alle Kombinationen eines Zahlensystems "buddeln". Jetzt bleibt aber das Problem, dass man bei dieser Aufgabenstellung die Quersumme nicht verändern darf. Also muss jedes Mal, wenn eine Zahl "erniedrigt" wird, eine andere erhöht werden. Der logische erste Vektor ist dann natürlich (0, ..., n). Dann ist man schon so weit:
für k = 3, n = 3:
(0, 0, 3)
(0, 1, 2)
(0, 2, 1)
(0, 3, 0)

Hier findet dann der zweite "Überlauf" statt, genauso wie beim Zählen, nur dass man hier die Quersumme nicht verändern darf.
Beim zählen würde
(1, 0, 0)
folgen, die "am nächsten gelegene" Permutation wäre dann
(1, 0, 2)

Fertig.