4. Algorithmus zu Finden aller schwachen Kompostionen

Algorithmus zu Finden aller schwachen Kompostionen

  • F

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

    (n+k−1k−1)=(n+k−1n)\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.

    0
  • C

    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.

    0
  • C

    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.

    0
  • F

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

    0
  • C

    @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

    0
  • C

    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.

    0
  • F

    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.

    🙂

    0
  • C

    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. 🙂

    0
  • F

    Ah super,

    die Idee habe ich verstanden:) Jetzt weiß ich nicht mehr, wie ich im Code die Variablenwerte für n und k angebe. 😮 Muss ich sie in den Zeilen 26 und 27 initialisieren?

    Erstaunlich, dass die Ausgabe so viel Zeit in Anspruch nimmt 🙂

    Viele Grüße!

    0
  • C

    In cookies Code werden sie genau hier übergeben:

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

    Wenn du das in eine Funktion packen willst, die die Werte als Parameter übernimmt, bleiben nur die vector<>-Operationen übrig:

    v.resize(k);
v[0]=n;

    PS: Daß die Ausgabe so viel Zeit in Anspruch nimmt, überascht mich jetzt nicht wirklich 😉 Davon dürfte das meiste von Windows verbraten werden, das nach jeder Ausgabe das Konsolenfenster neu zeichnet.

    Afair hatte volkard vor einer Weile mal was zu der Thematik gesagt. Ich gehe mal auf die Suche.

    0
  • C

    firfan schrieb:

    Erstaunlich, dass die Ausgabe so viel Zeit in Anspruch nimmt 🙂

    Eigentlich nicht. 🙂
    Du musst bedenken, was jeder Grafikcall an Rechenkraft kostet! Jeder Pixel muss einzeln gesetzt werden, das dauert ewig.

    firfan schrieb:

    Jetzt weiß ich nicht mehr, wie ich im Code die Variablenwerte für n und k angebe.

    Guck dir noch mal meinen Code oben an. Da kannst du n und k angeben, wie du möchtest. Ansonsten: die Größe des Vektors ist gleich k, n wird der Funktion ja übergeben. (Der Parameter heißt auch n.)

    Allerdings solltest du dringend die C++ Grundlagen lernen, falls du solche Aufgaben noch öfter zu erwarten hast.

    0
  • F

    Danke, dass ihr so hilfsbereit seid. Ja, ich brauche unbedingt ein gutes C++ Buch, dass mir die Grundlagen strukturiert erklärt.

    Was mache ich falsch, wenn meine main-funktion so aussieht. "count" stimmt nicht mehr mit meiner Rechnung überein. 😕

    int main()
{
  int n = 30;
  int k = 5;
  std::vector<int> v;

  while (1)
  {
    v.clear();
    v.resize(k);
    v[0] = n;

    int count = 0;

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

    std::cout << "count: " << count << std::endl;
    std::cout << "----------" << std::endl;
  }
} 
}
    0
  • C

    Du hast vermutlich die Ausgabe(?)-Anweisung in der for-Schleife weggelassen - und dadurch bezieht sich das for() jetzt auf die nächste verfügbare Anweisung: ++count;

    0
  • F

    Ah stimmt, daran liegt's! 🙄 Jetzt funktioniert alles einwandfrei. Es werden alle Kompositionen gefunden. Ich verwende die Kompositionen als Input für eine andere Funktion, worüber ich mir jetzt ein paar Gedanken machen werde.

    Vielen herzlichen Dank für eure Hilfe!!! Ihr seid spitze! 👍

    0
Anmelden zum Antworten