Zähl-Algorithmus

[Erik (Gast)]

Hallo,

ich weiß nicht ob ich hier richtig bin aber ich versuchs mal:

ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array 
durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu 
einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array 
konstant bleiben muss. Beispiel:

4 Felder und gewünschte Summe ist 6 und mögliche Zahlen in den Feldern 
sind 1 und 2, also gibt es 6 Kombinationen:

1.1.2.2 ; 1.2.1.2 ; 1.2.2.1 ; 2.1.1.2 ; 2.1.2.1 ; 2.2.1.1

ich hab erstmal eine simplen Zähl-Algorithmus programmiert der (für 
dieses Beispiel) alle 16 möglichen Kombinationen durchzählt und jedes 
mal aufsummiert und prüft ob die Summe passt, das ist natürlich extrem 
ineffizient (in meinem realem Problem sind die Kombinationsmöglichkeiten 
deutlich zahlreicher, mein Beispiel hier ist kras vereinfacht, und da 
ist Brute-Force keine gute Lösung).

Ich suche also einen Zähl-Algorithmus der mein Problem elegant lößt aber 
ich komme auf keine Lösung, irgendwie scheint mein Hirn aktuell ein 
Problem mit Mathematik zu haben.

Hat hier irgendjemand eine Idee?

Grüße Erik

[Tilo R. (joey5337)]

Wie groß ist dein Alphabet, d.h. welche Ziffern lässt du zu?

In deinen Beispielen oben gibt es nur die Ziffern 1 und 2, und immer 
jeweils 2 davon. Diese Kombinationen lassen sich einfach enumerieren:

1. Schritt: Position der ersten 2 festlegen (erste bis dritte Stelle, 3 
Möglichkeiten)
2. Schritt: Position der zweiten 2 festlegen (nachfolgende bis letzte 
Stelle, 3 bis eine Möglichkeit)

[Erik (Gast)]

> Wie groß ist dein Alphabet, d.h. welche Ziffern lässt du zu?

In meinem realem Problem ist das nicht fest definiert, ich benötige 
einen generischen Algorithmus der mit den 4 Parametern:
- Anzahl Felder
- gewünsche Summe
- kleinstmögliche Zahl (ist in reality meist 2 oder 3, muss größer als 0 
sein)
- größtmögliche Zahl (ist meist im Rahmen von 20 bis 30 kann aber auch 
größer sein)

Reine binäre Sachen reichen mir leider nicht, sorry das ich mein 
Beispiel zu stark oversimplified hab.

Grüße
Erik

[Jobst Q. (joquis)]

Du könntest von der Gesamtsumme rückwärts zählen. Wenn 0 oder unter null 
kannst du abbrechen. Im Beispiel wenn schon in den ersten 3 Feldern eine 
zwei steht. Ebenso wenn die Restzahl zu klein ist (die ersten 3 Felder 
1)

Beim Beispiel bringt das nicht viel, aber bei vielen Feldern und großen 
Möglichkeitsbereichen kann das schon einiges ausmachen.

Wenn die Zellen nicht zufällig gefüllt und zu testen sind, sondern 
nacheinander alle Möglichkeiten, kannst du damit von vornherein ganze 
Blöcke ausschließen.

[Tilo R. (joey5337)]

Ich würde eine Tiefensuche machen, jede Ebene steht für eine Ziffer, der 
Wurzelknoten für die erste Ziffer, Blätter für die letzte.
Unterwegs die Quersumme mitrechnen, dann ist die letzte Ebene einfach.

Zum nächsten Zählerinkrement kommst du folgendermaßen:
1. du erhöhst dir vorletzte Stelle um 1. Tiefensuche auf niedrigeren 
Ebenen liefert dir die letzte Stelle (Rest zur Quersumme).
Wenn erhöhen nicht mehr geht oder die Tiefensuche keine Lösung liefert 
(Quersumme zu groß), dann musst du eine weitere Stelle nach vorne gehen 
und die um eins erhöhen. Tiefensuche ab da liefert dir wieder die 
kleinstmögliche passende Kombination.

Wenn es dann immer noch keine Lösung gibt: eine Stelle weiter nach vorne 
etc.

Nachtrag:
Jobst Q. hat natürlich recht, untaugliche Bäume so früh wie möglich zu 
überspringen (Pruning).
Es bietet sich an, das Alphabet auf 0..x zu ändern (und die Quersumme 
entsprechen anzupassen - ist ja nur eine Verschiebung). Dann musst du 
für das Pruning nur die "Quersumme zu groß"-Prüfung machen.

[flip (Gast)]

meinst du sowas in der art?

#include <stdio.h>

void find_combinations(int fields[], int num_fields, int sum, int current_sum, int current_field) {
    if (current_field == num_fields) {
        if (current_sum == sum) {
            printf("Kombination gefunden: ");
            for (int i = 0; i < num_fields; i++) {
                printf("%d ", fields[i]);
            }
            printf("\n");
        }
        return;
    }

    // Versuche alle möglichen Werte für das aktuelle Feld
    for (int i = 1; i <= 2; i++) {
        fields[current_field] = i;
        find_combinations(fields, num_fields, sum, current_sum + i, current_field + 1);
    }
}

int main() {
    int fields[4];
    find_combinations(fields, 4, 6, 0, 0);
    return 0;
}

In diesem Code wird die rekursive Funktion "find_combinations" 
verwendet, um alle möglichen Kombinationen von Feldern zu finden, die 
die Summe 6 ergeben. Die Funktion nimmt als Parameter das Array der 
Felder, die Anzahl der Felder, die gewünschte Summe, die aktuelle Summe 
und das aktuelle Feld. Innerhalb der Funktion wird überprüft, ob alle 
Felder gezählt wurden. Wenn ja, wird überprüft, ob die aktuelle Summe 
der gewünschten Summe entspricht. Wenn ja, wird die aktuelle Kombination 
ausgegeben. Wenn nein, wird die Funktion beendet. Wenn nicht alle Felder 
gezählt wurden, werden alle möglichen Werte für das aktuelle Feld 
ausprobiert und die Funktion erneut aufgerufen.

[Tilo R. (joey5337)]

flip schrieb:
> meinst du sowas in der art?

Genau! Das ist eine Tiefensuche, rekursiv programmiert.
Die Traversiert einmal den kompletten Baum und liefert alle gültigen 
Kombinationen in der richtigen Reihenfolge.

Dass muss der TO jetzt erweitern, so dass nicht nur 1 und 2 als gültige 
Symbole verwendet werden.

Dann gibt es noch Optimierungsmöglichkeiten, z.B. die genannten 
Suchbaumeinschränkungen, wenn in der Rekursion weiter unten keine 
Lösungen mehr möglich sind.
Ebenso kann man die Rekursion entsprechend umbauen, dass nicht alle 
Lösungen ausgegeben werden sondern nur die nächste gesucht wird.

[Johann L. (gjlayde)]

Nennt sich "Partitionierung" und hat eine ganz interessante Theorie, 
siehe etwa https://de.wikipedia.org/wiki/Partitionsfunktion und Freunde.

Eine Möglichkeit, Partitionen zu bestimmen ist rekursiv:

Um zum Beispiel 6 in 1en und 2en zu zerlegen, nimmt man Partitionen von 
4 und nimmt zur Menge der Teile 2 hinzu, oder man nimmt Partitionen von 
5 und nimmt zur Menge der Teile 1 hinzu.

Hier in C hingeschlunzt:

#include <stdio.h>
#include <stdlib.h>

// Erlaubte Summanden.
static const int parts[] = { 1, 2 };

#define ARRAY_SIZE(X) (int) (sizeof(X) / sizeof(*X))

#define MAX_PARTS 100

// Tatsaechlich verwendete Summanden.
int a[MAX_PARTS];

void output (int n_parts)
{
    for (int i = 0; i < n_parts; ++i)
        printf (" %d", a[i]);
    printf ("\n");
}

// Partitioniere n in n_summands Summanden (falls n_summands > 0).
// Partitioniere n (falls n_summands == -1).
// Partitioniere n (falls n_summands == -2).
void decompose (int n, int n_parts, int n_summands)
{
    if (n == 0)
    {
        if (n_summands < 0 || n_parts == n_summands)
            output (n_parts);
    }
    else if (n > 0)
    {
        for (int i = 0; i < ARRAY_SIZE (parts); ++i)
        {
            if (n_summands == -2 && n_parts > 0 && a[n_parts - 1] > parts[i])
                continue;

            if (n_parts >= MAX_PARTS)
            {
                fprintf (stderr, "\nerror: Array a[%d] zu klein!\n", MAX_PARTS);
                exit (1);
            }
            a[n_parts] = parts[i];
            decompose (n - parts[i], 1 + n_parts, n_summands);
        }
    }
}

int main (void)
{
    int n = 6;
    int n_summands = 4;

    printf ("n = %d in %d Summanden:\n", n, n_summands);
    decompose (6, 0, 4); // Immer 4 summanden

    printf ("n = %d in beliebig viele Summanden:\n", n);
    decompose (6, 0, -1);

    printf ("n = %d in beliebig viele Summanden (monoton wachsend):\n", n);
    decompose (6, 0, -2);
}

**Ausgabe**

n = 6 in 4 Summanden:
 1 1 2 2
 1 2 1 2
 1 2 2 1
 2 1 1 2
 2 1 2 1
 2 2 1 1
n = 6 in beliebig viele Summanden:
 1 1 1 1 1 1
 1 1 1 1 2
 1 1 1 2 1
 1 1 2 1 1
 1 1 2 2
 1 2 1 1 1
 1 2 1 2
 1 2 2 1
 2 1 1 1 1
 2 1 1 2
 2 1 2 1
 2 2 1 1
 2 2 2
n = 6 in beliebig viele Summanden (monoton wachsend):
 1 1 1 1 1 1
 1 1 1 1 2
 1 1 2 2
 2 2 2

So wie der Code steht, bestimmt er nur Partitionen, die aus Summanden 
aus parts[] bestehen, hier also 1 und 6. Mann man beliebige natürliche 
Summanden zulassen will, braucht's ne kleine Erweiterung.

[Michael B. (laberkopp)]

Erik schrieb:
> ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array
> durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu
> einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array
> konstant bleiben muss.

Du willst also gar nicht zählen.

Du willst permutieren.

Dafür gibt es viele fertige Funktionen.

Dann brauchst du bloss noch EINE Arraybelegung vorzugeben, die mit den 
erlaubten Zahlen deine Summe ergibt.

Und die kann z.B. im Array zuerst die grösste Zahl speichern, hinten die 
kleinste, und dazwischen den Rest verteilen. Wenn es 6 als Summe von 1 
und 2 im Feld sein soll gibt es halt nur 2,2,1,1

Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es

9,1,0,0
8,2,0,0
8,1,1,0
7,3,0,0
7,2,1,0
7,1,1,1
6,4,0,0
6,3,1,0
6,2,2,0
6,2,1,1
5,5,0,0
usw. bis
3,3,3,1
3,3,2,2

[Johann L. (gjlayde)]

Michael B. schrieb:
> Du willst permutieren.

Für dieses einfache Beispiel schon, im allgemeinen trifft dies aber 
nicht zu:

Angenommen, wir wollen 6 zerlegen in 2 Summanden aus { 1, 2, 3, 4, 5, 6 
}.  Mögliche Zerlegungen sind dann:

1 + 5, 2 + 4, 3 + 3, 4 + 2 und 5 + 1

und i.d.R sind dies nicht Permutationen voneinander.

[Jobst Q. (joquis)]

Erik schrieb:
> - Anzahl Felder
> - gewünsche Summe
> - kleinstmögliche Zahl (ist in reality meist 2 oder 3, muss größer als 0
> sein)
> - größtmögliche Zahl (ist meist im Rahmen von 20 bis 30 kann aber auch
> größer sein)

Die Zahl der Parameter kann man reduzieren, indem man die 
kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu 
nimmt. Dann hat man immer einen Bereich von 0 bis x.

Bei einem Bereich von 20 bis 30 muss aber die Zahl der Felder beschränkt 
werden, sonst wird die Zahl der Kombinationen (Bereich hoch Felder) 
astronomisch.

[Michael B. (laberkopp)]

Johann L. schrieb:
> Für dieses einfache Beispiel schon, im allgemeinen trifft dies aber
> nicht zu:

Was meinst du, warum ich das zweite Beispiel mit den möglichen 
Vorbelegungen des fann zu permutierenden Arrays schon beschrieben hatte 
?

Damit auch du es liest !

[Jobst Q. (joquis)]

Michael B. schrieb:
> Erik schrieb:
>> ich benötige einen Zähl-Algorithmus bei dem die Felder in einem Array
>> durchgezählt werden sollen, von einer minimalen Zahl im Feld bis zu
>> einer maximalen Zahl im Feld, aber die Summe über alle Felder im Array
>> konstant bleiben muss.
>
> Du willst also gar nicht zählen.
>
> Du willst permutieren.
>
> Dafür gibt es viele fertige Funktionen.
>
> Dann brauchst du bloss noch EINE Arraybelegung vorzugeben, die mit den
> erlaubten Zahlen deine Summe ergibt.
>
> Und die kann z.B. im Array zuerst die grösste Zahl speichern, hinten die
> kleinste, und dazwischen den Rest verteilen. Wenn es 6 als Summe von 1
> und 2 im Feld sein soll gibt es halt nur 2,2,1,1

>
> Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es
>
> 9,1,0,0
> 8,2,0,0
> 8,1,1,0
 Und was ist mit
9,0,1,0
9,0,0,1
8,0,2,0
8,0,0,2
...
Vollständig ist die so generierte Liste jedenfalls nicht.

Aber der Ansatz, nicht alle möglichen Kombinationen durch zu testen, 
sondern zutreffende Kombinationen systematisch abzuändern, ist sehr gut. 
Ob da Permutation noch der passende Ausdruck ist, ist unwesentlich. Eine 
klassische Permutation ist es wohl nicht.

Sehr praktisch ist, dass man eine solche Funktion rekursiv anwenden 
kann.
Im Beispiel um alle Kombinationen mit 9 im ersten Feld zu finden, ruft 
man die Funktion mit Felder=3, Quersumme=1, Bereich = 2 (0 bis 1) auf.
Bei 8 am Anfang mit Felder=3, Quersumme=2, Bereich = 3 (0 bis 2).
Bei 7 am Anfang mit Felder=3, Quersumme=3, Bereich = 4 (0 bis 3).
usw.

[Erik (Gast)]

Hallo,

Danke für die zahlreichen Antworten!


von Johann L. schrieb:
> Nennt sich "Partitionierung" und hat eine ganz interessante Theorie,
> siehe etwa https://de.wikipedia.org/wiki/Partitionsfunktion und Freunde.
Ja, das sieht sehr interessant aus, aber da werde ich ne Weile für 
brauche bis ich da durchgestiegen bin. Beim schnellen überfliegen des 
Wikipedia-Artikel hab ich leider keine Lösung für effizientes ermitteln 
gesehen. Mein Problem ist das die Gesamtanzahl der möglichen Muster 
(Größe-Alphabet hoch Anzahl-Felder) im Bereich 10^9 bis 12^12 liegt (und 
wir haben hier eine Variante wo die Komplexität für 
Brute-Force-Durchzählen bei etwa 10^20 ist, das ist auch für einen 
modernen PC mit GHz-CPU zu viel so das wir das bis jetzt noch nichtmal 
probiert haben).

Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen 
kann wie viele Rekursionsebenen es werden könnten und man da ja 
aufpassen muss das der Stack nicht ausgeht.


von Michael B. schrieb:
> Du willst also gar nicht zählen.
> Du willst permutieren.

Ob man das nun Permutation nennt ist mir egal aber ich hatte die 
Vermutung das wenn ich eine Zahl um eins erhöhe da ich dann eine andere 
Zahl um eins verringern muss das es da eventuell einen Algorithmus gibt 
der genau das leistet und somit alle "gültigen" Varianten findet ohne 
dafür Brute-Force-Durchzählen benutzen zu müssen.

von Michael B. schrieb:
> Wenn es 10 sein soll und alle Ziffern von 0 bis 9 gibt es
> 9,1,0,0
> 8,2,0,0
> ...
in diesem Beispiel gibt es 282 "gültige" Kombinationen aber eben 10000 
simple Zähl-Möglichkeiten. Leider habe ich nichtmal eine Methode mit der 
ich die 282 ausrechnen kann, aktuell muss ich meinen Algorithmus einfach 
laufen lassen wenn ich auch nur wissen will wie viele gültige 
Möglichkeiten es gibt.

Hat dafür schonmal jemand eine Idee?


von Tilo R. schrieb:
> Dann gibt es noch Optimierungsmöglichkeiten, z.B. die genannten
> Suchbaumeinschränkungen, wenn in der Rekursion weiter unten keine
> Lösungen mehr möglich sind.
In meiner aktuellen Lösung hab ich schon einige Optimierungen so das 
wenn die gewünschte Quersumme schon in den ersten paar Felder 
erreicht/überschritten wird das dann nicht mehr bis zum letzten Feld 
stur inkrementiert wird sondern schon in einem vorderen Feld und die 
nachfolgenden Felder alle wieder auf den minimalen Wert gesetzt werden. 
Ich kann nicht genau sagen wie viel das einspart aber ich war etwas Zeit 
damit beschäftigt sicher zu beweisen das mir dadurch keine "gültigen" 
Kombinationen verloren gehen.


von Jobst Q. schrieb:
> Die Zahl der Parameter kann man reduzieren, indem man die
> kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
> nimmt. Dann hat man immer einen Bereich von 0 bis x.
Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand 
reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte 
durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen 
Unterschied in der Anzahl der Rechenschritte. Ich habe dann nur den 
zusätzlichen Aufwand am Ende für die Ausgabe jedes mal noch ein Offset 
dazuaddieren zu müssen (das sind Anzahl-Felder zusätzliche Additionen). 
Oder übersehe ich hierbei irgendetwas? Bitte korrigiere mich wenn ich 
falsch liege.


Grüße Erik

[Johann L. (gjlayde)]

Brauchst du den explizit alle Ergebnisse oder genügt die Anzahl 
möglicher Ergebnisse?

[Erik (Gast)]

Johann L. schrieb:
> Brauchst du den explizit alle Ergebnisse oder
> genügt die Anzahl möglicher Ergebnisse?
Ich benötige am Ende in jedem Fall alle Ergebnisse in einer XML-Datei.
Zur Vereinfachung wäre es schön wenn ich vorher ausrechnen könnte wie 
viele es werden aber das ist eher optional da es mir die eigentlich 
Arbeit nicht erspart.

[Michael B. (laberkopp)]

Jobst Q. schrieb:
> Und was ist mit
> 9,0,1,0
> 9,0,0,1
> 8,0,2,0
> 8,0,0,2
> ...
> Vollständig ist die so generierte Liste jedenfalls nicht.

Das sind Permutationen von 9,1,0,0 und 8,2,0,0.

Daher muss er permutieren, nicht zählen.

Weisst du mit dem Begriff Permutation nichts anzufangen ?

Die Startwerte habe ich genannt, deren Erzeugung ist trivial.

[Michael B. (laberkopp)]

Erik schrieb:
> aber ich hatte die Vermutung das wenn ich eine Zahl um eins erhöhe da
> ich dann eine andere Zahl um eins verringern muss

Ja.

Damit machst du dich bzw. deinen uC wegen Überarbeitung tot.

Daher besser einen Weg der nicht 10000 Mal probiert.

[Erik (Gast)]

Michael B. schrieb:
> Daher muss er permutieren, nicht zählen.
Okay, hab ich verstanden und klingt logisch.

Also hab ich für Dein Beispiel mit den 4 Feldern mal geschaut wie viele 
Permutationen möglich sind und das sind 4! = 24. Das scheint doch 
machbar bis ich ausrechnen wollte wie viele Startwerte es dann geben 
muss also 282:24 und das ist 11.75 und das scheint mir nicht aufzugehen. 
Irgendwo ist also bis hier noch ein Denkfehler drin. Dann ist mir 
aufgefallen das z.B. bei dem Muster 9.1.0.0 eben keine 24 Permutationen 
möglich sind sondern weniger weil die 0 doppelt vorkommt und ich bei den 
fertigen Mustern keine Dupletten erzeugen darf. Ich muss alle gültigen 
Muster finden und darf aber auch keines doppelt nennen. Das bedeutet das 
ich nach jedem Permutationsdurchgang immer noch alle Dupletten 
ausfiltern muss, das ist bei 24 möglichen Permutationen für 4 Felder 
sicher machbar aber wenn es 10 Felder werden und damit 3'628'800 
Permutationen wird das Ausfiltern von Dupletten doch sehr aufwendig. 
Falls es mal 20 Felder werden und damit 2'432'902'008'176'640'000 
Permutationen wird das Ausfiltern von Dupletten aber eher unmöglich (ich 
fürchte ich finde keinen Computer mit ausreichend RAM).

Ich bin mir nicht sicher aber intelligentes Zählen, bei dem direkt von 
einem gültigen Muster zum nächsten "gezählt" wird, scheint mir doch 
realistischer als Lösungsansatz.

Bitte korrigiere mich wenn ich falsch liege.

Michael B. schrieb:
> Daher besser einen Weg der nicht 10000 Mal probiert.
Ach, sag blos. ;)

Ungefähr das war mein Gedanke als ich diesen Thread gestartet hatte. Bei 
unseren richtigen Aufgaben liegt die Komplexität bei etwa 10^9 bis 10^12 
und nicht nur bei 10^4. Eventuell kommt sogar mal eine Aufgabe mit der 
Komplexität von etwa 10^20 auf mein fertiges Programm zu.

Grüße Erik

[Jobst Q. (joquis)]

Erik schrieb:

> Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen
> kann wie viele Rekursionsebenen es werden könnten und man da ja
> aufpassen muss das der Stack nicht ausgeht.

Das lässt sich sehr gut abschätzen. Wie ich es beschrieben habe, ist die 
Rekursionstiefe gleich der Anzahl der Felder. Und die ist ja nicht so 
hoch.


> von Jobst Q. schrieb:
>> Die Zahl der Parameter kann man reduzieren, indem man die
>> kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
>> nimmt. Dann hat man immer einen Bereich von 0 bis x.
> Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand
> reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte
> durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen
> Unterschied in der Anzahl der Rechenschritte. Ich habe dann nur den
> zusätzlichen Aufwand am Ende für die Ausgabe jedes mal noch ein Offset
> dazuaddieren zu müssen (das sind Anzahl-Felder zusätzliche Additionen).
> Oder übersehe ich hierbei irgendetwas? Bitte korrigiere mich wenn ich
> falsch liege.

Die kleinste Zahl als Offset brauchst du nur in der Ausgabe. Ansonsten 
wird alles einfacher, da der Bereich immer mit 0 anfängt und du einen 
Parameter einsparst. Durch die vielfache Rekursion, die aber nicht tief 
geht, wird das bedeutsam.

Nicht ganz trivial ist die Ausgabe der gefundenen Kombinationen. Ich 
würde vorschlagen, das als String an eine Ausgabefunktion zu übergeben. 
Für 0 bis 9 gehen die Dezimalziffern, für weitere Zahlen kann man sie 
einfach nach oben erweitern. 10 wäre dann ':', 11 ';', usw.

Als Eingangsparameter käme zu Felder, Quersumme und Bereich noch ein 
Stringzeiger auf die ersten Felder dazu. Also "62" und Felder=2, 
Quersumme=2, Bereich = 3, um im obigen Beispiel (Felder=4, Quersumme=10, 
Bereich = 10) die Kombinationen mit 6 und 2 in den ersten Feldern 
auszugeben. Damit kann die Ausgabefunktion mit dem String "6202", "6211" 
und weiteren bedient werden.

[Michael B. (laberkopp)]

Erik schrieb:
> ich bei den fertigen Mustern keine Dupletten erzeugen darf.

Es gibt die dafur passenden Permutationsfunktionen.

[Jobst Q. (joquis)]

Michael B. schrieb:
> Jobst Q. schrieb:
>> Und was ist mit
>> 9,0,1,0
>> 9,0,0,1
>> 8,0,2,0
>> 8,0,0,2
>> ...
>> Vollständig ist die so generierte Liste jedenfalls nicht.
>
> Das sind Permutationen von 9,1,0,0 und 8,2,0,0.

Das ist mir inzwischen auch klar geworden.

Ich finde es aber umständlich, erst Startwerte zu suchen und auf die 
dann Permutationsfunktionen loszulassen. Nur eine Funktion rekursiv zu 
nutzen, scheint mir da doch einfacher. Keep it simple. Komplizierter 
wird es von allein.

[Tilo R. (joey5337)]

Erik schrieb:
> gesehen. Mein Problem ist das die Gesamtanzahl der möglichen Muster
> (Größe-Alphabet hoch Anzahl-Felder) im Bereich 10^9 bis 12^12 liegt (und
> wir haben hier eine Variante wo die Komplexität für
> Brute-Force-Durchzählen bei etwa 10^20 ist, das ist auch für einen
> modernen PC mit GHz-CPU zu viel so das wir das bis jetzt noch nichtmal
> probiert haben).
Mach mal ein konkretes Beispiel: Symbole von-bis, Anzahl der Stellen und 
Quersumme.

10^20 sind ungefähr 14 Stellen mit einem 25-er Alphabet. Es hängt extrem 
von der Quersumme ab, wie viel tatsächliche Kombinationen es gibt. 
(Worst Case sind hier "mittlere" Werte.)

Vergiss im übrigen das Partitionierungs-Gedöns, und Permutationen. Das 
ist nice zu wissen, hilft dir hier konkret aber nicht. Alles wo du 
hinterher Dubletten rausfiltern musst bringt dir auch nichts, weil du 
dazu alle Lösungen zwischenspeichern müsstest. Du willst einmal, 
geordnet den kompletten Lösungsraum durchschreiten. Nicht mehr, aber 
auch nicht weniger.

> Einen rekursiven Algorithmus möchte ich vermeiden da ich kaum abschätzen
> kann wie viele Rekursionsebenen es werden könnten und man da ja
> aufpassen muss das der Stack nicht ausgeht.
Keine Angst, die rekursiven Algorithmen haben nur so viele Ebenen wie du 
Stellen hast.
Wenn du eine rekursive Lösung hast kann man das jederzeit zu einer 
iterativen Lösung umbauen. Das ist eine Programmierübung die man eh ein 
paar mal üben sollte.

Wenn du alle Lösungen haben willst ist es unvermeidbar, den ganzen Baum 
ein mal komplett durchzugehen.

Wenn du zählen willst, wie viele Lösungen es gibt empfehle ich einen 
Dynamic-Programming-Ansatz: Du gehst ganz normal rekursiv den Baum 
durch, aber lässt dir die Anzahl der gefundenen Lösungen als 
Funktionsergebnis liefern. Zusätzlich speicherst du die Teilergebnisse 
in einem Cache. Als Key die Anzahl Stellen und die Quersumme, als Value 
die Zahl der gefundenen Lösungen.
Bei einem Alphabet 2..9 würde da z.B. stehen:

2 Stellen, Quersumme 4: 1 Lösung
2 Stellen, Quersumme 5: 2 Lösungen
2 Stellen, Quersumme 14: 5 Lösungen
2 Stellen, Quersumme 15: 4 Lösungen

und natürlich später auch Lösungen für 3 Stellen, 4 Stellen etc.
Wenn du dann in Zukunft bei der Rekursion nochmal absteigen musst kannst 
du stattdessen den gespeicherten Wert verwenden.

Wenn man an dieser Stelle das Hirn noch etwas weiter verknoten will 
kommt man drauf, dass man die Rekursion gar nicht braucht und dass man 
die Ergebnisse von z.B. 3-Stellen aus den 2-Stellen-Ergebnissen 
berechnen kann. Und dass man die 2-Stellen-Ergebnisse danach nicht mehr 
braucht.
Das ganze kann man dann mit 2 Arrays und einer 3-fach geschachtelten 
Schleife ausrechnen (außen aufsteigend Anzahl Stellen, innen 
Alphabet-Symbole und Quersummen-Werte). Das geht in die Richtung, wo die 
Partitionierungs-Algorithmen helfen.

[Tilo R. (joey5337)]

Erik schrieb:
> von Jobst Q. schrieb:
>> Die Zahl der Parameter kann man reduzieren, indem man die
>> kleinstmögliche Zahl als Offset abzieht und erst zur Ausgabe wieder dazu
>> nimmt. Dann hat man immer einen Bereich von 0 bis x.
> Okay, ich verstehe nur nicht in welcher weise das meinen Rechenaufwand
> reduziert. Ob ich in einem Feld von 3 bis 10 für 8 Schritte
> durchinkrementiere oder von 0 bis 7 macht aus meiner Sicht keinen
> Unterschied in der Anzahl der Rechenschritte.

Angenommen du hast noch 3 Stellen übrig. Dann gibt es folgende 
Abbruchkriterien:

Rest-Quersumme > 3 x 10   // alle verbleibenden Stellen auf max
Rest-Quersumme < 3 x 3    // alle verbleibenden Stellen auf min

Das sind 2 Prüfungen. Mit einem 0..7-Alphabet bleibt nur eine Prüfung:

Rest-Quersumme > 3 x 7

Das beruht auf der Annahme, dass du die <0-Prüfung in der nächsten 
Ziffern-Ebene bei der Einschränkung der Auswahlmöglichkeiten ohnehin 
machen würdest.
Der Zusatzaufwand bei der Ausgabe fällt weniger ins Gewicht, weil du nur 
"relativ" wenige Lösungen ausgeben musst.

Wie viel das bei dir tatsächlich spart musst du ausprobieren. Ich würde 
das vorerst mal außer acht lassen. Die Alphabetgrenzen würde ich in 
globale Konstanten o.ä. speichern, die muss man nicht ständig als 
Parameter mit durchreichen.

[Jobst Q. (joquis)]

Hier eine fertige Lösung von mir.

[Tilo R. (Gast)]

Ok, der Code funktioniert. Aber bitte kein Beispiel daran nehmen.

Keine sprechenden Variablennamen, zu viele Funktionsparameter die 
unnötig Stack verbrauchen, dann mit einem Buffer die ungeschickteste 
Möglichkeit zum Zahlen speichern gewählt, dafür dann bei jedem Aufruf 
nochmal einen Buffer allokieren und kopieren. Mit der potentiell 
unsicheren Kopierfunktion die sich auf die 0-Terminierung verlässt. Dann 
noch Pointer Arithmetik.
Die Optimierungen mit der 0-Kette und dem angepassten br bringen wenig, 
machen den Code dafür größer und kosten Eleganz.

Aber trotzdem Lob (ernst gemeint). An den Details kann man ja noch 
feilen.

[Karl Käfer (Gast)]

Erik schrieb:
> Reine binäre Sachen reichen mir leider nicht, sorry das ich mein
> Beispiel zu stark oversimplified hab.

Hm, ich hab's immer noch nicht richtig verstanden. Vielleicht könntest 
Du die Anforderungen etwas besser darstellen, wenn Du kurz erklären 
würdest, wozu Du so etwas brauchst, also etwas zum Anwendungsfall 
erzählst?

[Totomitharry (Gast)]

Also ich sehe da keinen algorithmus..

Das ist doch nur Felder lesen, alles skippen wenn die Summe zu groß wird 
und wenn die Summe erreicht ist und das letzte Feld fertig ist, ein 
Match.

For Feld in Felder
Feldcnt++;
If(Feld<max&&Feld>min)tempsumme+=Feld
If(tempsumme>summe)Return False
If(Feldcnt==Felder)
If(tempsumme==Summe)Return true Else Return False

...

[Tilo R. (joey5337)]

Nachdem ich gestern Nacht noch so rumgemeckert habe musste ich heute 
auch mal eine Lösung bauen.
Haupterkenntnis für mich (wieder mal): ich hab keine Routine mehr in C.

Ich hab mich an Jobst Q.'s Code gehalten, Kommandozeilenparsing und 
Ausgabe kopiert. Was ich geändert habe ist, dass die Counter-Ausgabe 
auch bei abgeschaltetem output funktioniert (5. Parameter "o").

Überraschenderweise ist sein Code bei kleinen Quersummen schneller als 
meiner. Seine Optimierungen bringen da mehr als ich erwartet habe. 
(Nachfolgende Beispiele nutzen ein Alphabet von 2 bis 25)

Beispiel mit 10 Stellen und kleiner Quersumme (50):

$ time ./listqc  10 2 25 50 o
211865082 Kombinationen gefunden

real    0m6.685s
user    0m6.683s
sys     0m0.000s

$ time ./listqc-tre  10 2 25 50 o
211865082 Kombinationen gefunden

real    0m19.921s
user    0m19.919s
sys     0m0.000s

BTW: Der Bereich 2 bis 25 sind 24 mögliche Symbole, hoch 10 Stellen.
24^10 = 6,3 * 10^13.


Bei großen Quersummen fällt sein Code praktisch auf Brute-Force zurück. 
(7 Stellen, Quersumme 150):

$ time ./listqc-tre  7 2 25 150 o
736232 Kombinationen gefunden

real    0m0.067s
user    0m0.055s
sys     0m0.009s

$ time ./listqc  7 2 25 150 o
736232 Kombinationen gefunden

real    0m18.640s
user    0m18.637s
sys     0m0.000s

[TotoMitHarry (Gast)]

Das interessante ist ja auch, hast du einen Match, hast du ja mehrere 
Matches.. dann halt nur die gleichen Zahlen anders sortiert.

wenn du 1,1,1,2 gefunden hast weisst du das 1,1,2,1 und 1,2,1,1 und 
2,1,1,1 auch mit Summe 6 matchen werden.

wenn man jetzt die Generierung so gestaltet das diese Matches 
Zeitersparnis bringen könnte das bei großen Sachen noch schneller 
werden.

[Εrnst B. (ernst)]

TotoMitHarry schrieb:
> wenn man jetzt die Generierung so gestaltet das diese Matches
> Zeitersparnis bringen könnte

das ist das was oben unter dem Stichpunkt "Permutationen" schon 
ausführlich diskutiert wurde.

Du kannst den rekursiven Algorithmus einfach erweitern, dass der nur 
(absteigend) sortierte Möglichkeiten durchprobiert.

Als zweite Optimierung könnte der Algorithmus dann früher abbrechen, 
wenn die verbleibenden Zellen (die dann wegen der Sortierung <= dem 
aktuellen Wert sind) nicht mehr reichen, um die gewünschte Summe zu 
erreichen.

[Tilo R. (joey5337)]

Εrnst B. schrieb:
> Du kannst den rekursiven Algorithmus einfach erweitern, dass der nur
> (absteigend) sortierte Möglichkeiten durchprobiert.

Das wäre tatsächlich leicht machbar. Weil da Zahlen mehrfach vorkommen 
können wird es ziemlich kompliziert, das dann entsprechend zu 
permutieren.
Wenn ich z.B. die Quersumme 15 in 5 3 3 2 1 1 partitioniert habe, dann 
muss ich sowohl die doppelte 3 als auch die doppelte 1 beim permutieren 
berücksichtigen, damit ich keine Dubletten erzeuge.
Wenn es nur um das Zählen der Möglichkeiten könnte man durch die 
Häufigkeits-Fakultäten teilen. Aber nur zählen geht einfacher, ohne 
Rekursion, in O(Stellenzahl*Alphabetgröße*Quersumme).

Besser wäre es vielleicht, gleich nur die Partitionen (mit Häufigkeiten) 
zu suchen. Die Verteilung auf die einzelnen Stellen macht dann die 
Permutation.
Blöd ist, dass man bei der Permutationssuche nur Lösungen akzeptieren 
darf, wo die Stellenzahl genau stimmt. Das ist dann ähnlich wie in den 
jetzigen Lösungen die passende Quersumme prüfen.

Ich bin mir nicht sicher, wie viel man da tatsächlich spart. Problem 
sind in beiden Fällen "mittelgroße" Quersummen, weil da die Zahl 
möglicher Partitionen explodiert.

Es wäre gut wenn der TO tatsächliche Problemgrößen (und den 
Anwendungsfall) rausrücken könnte.

[Michael B. (laberkopp)]

Tilo R. schrieb:
> Das wäre tatsächlich leicht machbar. Weil da Zahlen mehrfach vorkommen
> können wird es ziemlich kompliziert

So so, in Mathe nicht aufgepasst ?

https://www.yaclass.at/p/mathematik/10-klasse/wahrscheinlichkeitsrechnung-19741/kombinatorik-21474/re-5a707527-a144-4a84-a4b6-d9e380467f11

[Totomitharry (Gast)]

Da ja die Felder in einem Array durchgezählt werden sollen könnte man 
die Permutationen in einer duplette einfach Nullen oder nur dort 
eintragen.

[Tilo R. (joey5337)]

Michael B. schrieb:
> Tilo R. schrieb:
>> Das wäre tatsächlich leicht machbar. Weil da Zahlen mehrfach vorkommen
>> können wird es ziemlich kompliziert
>
> So so, in Mathe nicht aufgepasst ?
Keine Sorge, Grundlagen in Wahrscheinlichkeitsrechnung und Kombinatorik 
sind noch da, auch wenn das schon ein paar Jährchen her ist.

Der Satz oben ging weiter: "das dann entsprechend zu permutieren."

Wenn du einen Algorithmus hast, der permutiert und dabei mehrfache 
Zahlen berücksichtigt, ohne dass man sich im Code einen abbricht, also 
mit einer gewissen Eleganz: immer her damit!
Ich lerne gerne dazu.

[Michael B. (laberkopp)]

Tilo R. schrieb:
> Wenn du einen Algorithmus hast, der permutiert und dabei mehrfache
> Zahlen berücksichtigt, ohne dass man sich im Code einen abbricht, also
> mit einer gewissen Eleganz: immer her damit!
> Ich lerne gerne dazu.

https://www.google.com/amp/s/www.geeksforgeeks.org/print-all-possible-permutations-of-an-array-with-duplicates-using-backtracking/amp/

Obwohl das erste Ergebnisbeispiel falsch ist, ist das wohl eine Lösung. 
Natürlich wird die Eleganz dich nicht befriedigen.

Man muss jedenfalls solche Algorithmen nicht neu erfinden, die gibt es 
fertig.

https://rosettacode.org/wiki/Permutations_with_some_identical_elements

[Jobst Q. (joquis)]

Tilo R. schrieb:
> Nachdem ich gestern Nacht noch so rumgemeckert habe musste ich heute
> auch mal eine Lösung bauen.
Danke Tilo, es hat mich sehr interessiert, wie andere das lösen.

Wie konnte ich nur die Möglichkeit übersehen, die auszugebenden Daten 
gleich in ein globales Array zu schreiben? Ich gehör ja nicht zu den 
Leuten, die globale Variablen verdammen, und finde es eher wichtig, die 
Parameterliste von Funktionen klein zu halten. Das ist etwas, was ich 
gerne von deinem Programm übernehme.

> Überraschenderweise ist sein Code bei kleinen Quersummen schneller als
> meiner. Seine Optimierungen bringen da mehr als ich erwartet habe.

Das hat mich auch interessiert. Ich habe daraufhin in beide Programme 
noch einen Zähler für die Anzahl der Rekursionen eingebaut. Und dabei 
festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da 
ist vielleicht noch etwas Spielraum für Optimierung. Es liegt vermutlich 
daran, dass ich den Zahlenbereich verändere, also reduziere, wenn 
möglich.

Festgestellt habe ich auch, dass bei mir die Zahl der Rekursionen gleich 
der der gefundenen Kombinationen ist, solange die gewünschte Quersumme 
kleiner oder gleich von Zahlenbereich + Felder ist. Merkwürdigerweise 
zeigt die Ausgabe mit r aber, dass nicht jede Rekursion eine Kombination 
findet.

> Bei großen Quersummen fällt sein Code praktisch auf Brute-Force zurück.
> (7 Stellen, Quersumme 150):

Auch das hat mir zu denken gegeben. Meine Lösung ist, die Reihenfolge 
bei der größeren Hälfte umzudrehen. War aber nicht ganz einfach und auch 
jetzt braucht es abwärts ein paar Rekursionen mehr als aufwärts.

Bei den Zeitmessungen habe ich auch festgestellt, dass die Ausgabe mit 
printf ein Vielfaches der Zeit des Findens beansprucht, zB das 30fache. 
Daraufhin habe ich mich um eine schnellere Ausgabe bemüht, mit direkter 
Stringprogrammierung und puts(). Um das zu vergleichen, kann ich die 
alte Methode mit Parameter s (für slow) erzwingen.

Hier die Vergleichstests mit den Parametern, die du auch verwendet hast. 
Auf einem Raspi Zero, wodurch Zeitunterschiede deutlicher werden als auf 
einem PC.

pi@raspips:~ $ ./test.sh 7 2 25 150
Parameter Felder:7 Min:2 Max:25 Quersumme:150
----------
./listqc2 7 2 25 150 o
736232 Kombinationen mit 906052 Rekursionen gefunden

real    0m0,806s
user    0m0,709s
sys     0m0,022s
----------
./listqc-tre 7 2 25 150 o
736232 Kombinationen mit 21745753 Rekursionen gefunden

real    0m2,020s
user    0m1,814s
sys     0m0,013s
----------
./listqc2 7 2 25 150 > /dev/null
736232 Kombinationen mit 906052 Rekursionen gefunden

real    0m2,108s
user    0m1,835s
sys     0m0,075s
----------
./listqc2 7 2 25 150 s > /dev/null
736232 Kombinationen mit 906052 Rekursionen gefunden

real    0m12,188s
user    0m9,789s
sys     0m0,221s
----------
./listqc-tre 7 2 25 150 > /dev/null
736232 Kombinationen mit 21745753 Rekursionen gefunden

real    0m12,329s
user    0m10,132s
sys     0m0,226s

[Jobst Q. (joquis)]

Michael B. schrieb:
> Obwohl das erste Ergebnisbeispiel falsch ist, ist das wohl eine Lösung.
> Natürlich wird die Eleganz dich nicht befriedigen.
>
> Man muss jedenfalls solche Algorithmen nicht neu erfinden, die gibt es
> fertig.

Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren 
Algorithmus erfinden muss, um diesen richtig zu füttern. Dann doch 
lieber nur einen Algorithmus aus einem Guss.

[Michael B. (laberkopp)]

Jobst Q. schrieb:
> Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren
> Algorithmus erfinden muss, um diesen richtig zu füttern.

Weils die halbe Arbeit ist

> Dann doch
> lieber nur einen Algorithmus aus einem Guss.

Divide and Conquer ist nicht dein Ding.

[Jobst Q. (joquis)]

Michael B. schrieb:
> Jobst Q. schrieb:
>> Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren
>> Algorithmus erfinden muss, um diesen richtig zu füttern.
>
> Weils die halbe Arbeit ist

Dann machs doch, dann können wir vergleichen.

[Tilo R. (joey5337)]

Jobst Q. schrieb:
> Und dabei
> festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da
> ist vielleicht noch etwas Spielraum für Optimierung. Es liegt vermutlich
> daran, dass ich den Zahlenbereich verändere, also reduziere, wenn
> möglich.
Der Faktor ist knapp über 24 - der Anzahl der Möglichkeiten pro Stelle. 
Ich hatte am Montag zeitweise auch einen zweiten Zähler eingebaut und 
kam auf den Faktor knapp über 10, als ich mit einem 10er-Alphabet 
getestet habe.
Der Grund ist, dass ich in der letzten Rekursionsstufe, wenn mit dem 
verbleibenden Quersummerest völlig klar ist, was die letzte Stelle sein 
muss, ich in der Schleife trotzdem alle möglichen Werte durchgehe und 
noch einmal in die Rekursion gehe.

Du hast in diesem Fall immerhin die obere Schranke abgedeckt, indem du 
die br-Variable entsprechend verkleinert hast.
Ich habe auch daran gedacht das zu machen indem die Schleife nur bis 
min(restquersumme, max_val) geht. Für die untere Grenze der Schleife ist 
mir leider nichts eingefallen.
Ich habe mich dann dagegen entschieden. Der Code würde komplizierter und 
die zusätzliche Abfrage müsste auch in den oberen Rekursionsstufen 
ausgeführt werden, wo sie wenig bringt. Und ich zahle nur einen 
konstanten Faktor dafür, das war mir egal.

Am effizientesten wäre wohl, die Rekursion immer in der vorletzten Stufe 
abzubrechen und die letzte Ziffer zu berechnen.
Wenn man die Sonderbehandlung weiterspinnt könnte man das prinzipiell 
auch für mehr als eine Stelle machen: bei gegebener Restquersumme gibt 
es ja immer die gleichen möglichen Endzifferfolgen, die könnte man 
Zwischenspeichern. CPU gegen Speicher.


Jobst Q. schrieb:
>> Bei großen Quersummen fällt sein Code praktisch auf Brute-Force zurück.
>> (7 Stellen, Quersumme 150):
>
> Auch das hat mir zu denken gegeben. Meine Lösung ist, die Reihenfolge
> bei der größeren Hälfte umzudrehen.
Das ist ein cooler Trick!

[Tilo R. (joey5337)]

Michael B. schrieb:
> Jobst Q. schrieb:
>> Was nützt ein fertiger Algorithmus, wenn man doch einen weiteren
>> Algorithmus erfinden muss, um diesen richtig zu füttern.
>
> Weils die halbe Arbeit ist
>
>> Dann doch
>> lieber nur einen Algorithmus aus einem Guss.
>
> Divide and Conquer ist nicht dein Ding.

jaja.

Wenn es ein Alphabet mit a unterschiedlichen Möglichkeiten pro Ziffer 
gibt und insgesamt d Stellen belegt werden sollen, dann spart die Suche 
nach Partitionen (d.h. absteigender Ziffernfolgen) anstelle aller 
gültigen Ziffernfolgen ganz grob den Faktor (1/2)^d ein. Dafür müssen 
dann für jede gefundene Lösung die Permutationen gesucht werden, was 
einen Faktor O(d^2) kostet.

Ob Partitionen+Permutation wirklich "die halbe Arbeit" gegenüber der 
deutlich einfacheren Tiefensuche ist, hängt erheblich von den Parametern 
der Aufgabenstellung ab.
Wenn wegen der Quersumme nur wenige Lösungen gefunden werden und/oder 
nur wenige Stellen besetzt werden müssen, kann das vorteilhaft sein.
Andererseits scheinen die gezeigten Lösungen dem Problem des TO 
angemessen leistungsfähig zu sein.

Mich würde allerdings schon interessieren, ob du den von dir 
vorgeschlagenen Weg implementiert bekommen würdest und wie verständlich 
der Code dann ist.
Du hast immerhin den Vorteil, gegen mehrere funktionierende 
Referenzimplementierungen testen zu können.

[Michael B. (laberkopp)]

Jobst Q. schrieb:
> Dann machs doch, dann können wir vergleichen

Es ist nicht meine Hausaufgabe.

[Tilo R. (joey5337)]

Jobst Q. schrieb:
> Ich habe daraufhin in beide Programme
> noch einen Zähler für die Anzahl der Rekursionen eingebaut. Und dabei
> festgestellt, dass diese bei deinem listqc-tre deutlich höher ist. Da
> ist vielleicht noch etwas Spielraum für Optimierung.

Danke für den Ansporn darüber nachzudenken!
Durch umsortieren und weglassen konnte ich noch eine Größenordnung 
rausholen. (Ich musste die Aufgabe schwieriger machen weil ich keinen 
PiZero übrig habe.)

Parameter Felder:8 Min:2 Max:25 Quersumme:75
----------
./listqc 8 2 25 75 o
563853888 Kombinationen gefunden

real    0m33.925s
user    0m33.923s
sys     0m0.000s
----------
./listqc2 8 2 25 75 o
563853888 Kombinationen mit 595752418 Rekursionen gefunden

real    0m11.433s
user    0m11.431s
sys     0m0.000s
----------
./listqc-tre 8 2 25 75 o
563853888 Kombinationen mit 14983409377 Rekursionen gefunden

real    0m44.820s
user    0m44.817s
sys     0m0.000s
----------
./listqc-tre2 8 2 25 75 o
563853888 Kombinationen mit 1450916065 Rekursionen gefunden

real    0m5.048s
user    0m5.046s
sys     0m0.000s

Bei so Optimierungssachen finde ich es immer wieder beeindruckend, wie 
wichtig kleine Details sind, die man im fertigen Code gar nicht mehr 
sieht.

Ich fand das bei projecteuler manchmal so krass, wenn ich nach 3 Tagen 
mit riesigem Aufwand das Ergebnis geradeso rausbekommen habe, und im 
Forum postet dann jemand einen 5-Zeiler der mehrere Größenordnungen 
schneller ist.
Mit den neueren Aufgaben dort kann ich leider nicht so viel anfangen. 
Die sind mir zu mühsam, bei vielen habe ich nicht mal den Hauch einer 
Idee.

[Tilo R. (joey5337)]

@Erik:
Hey TO, wie passen denn die gefundenen Lösungen zu deiner tatsächlichen 
Aufgabenstellung?

[Jobst Q. (joquis)]

Tilo R. schrieb:
> Bei so Optimierungssachen finde ich es immer wieder beeindruckend, wie
> wichtig kleine Details sind, die man im fertigen Code gar nicht mehr
> sieht.
>

Ich muss zugeben, dass dein Algorithmus trotz mehr Rekursionen schneller 
ist, vor allem bei vielen Kombinationen. Vermutlich liegt es doch daran, 
dass deiner nur 2 Parameter hat und meiner 3.

Aber Optimierungsbedarf hat dein Programm bei der Ausgabe. Die 
printf-Funktion ist eben ziemlich komplex und der Aufruf für jede Zahl 
bremst gewaltig.

Hier die Vergleiche mit Ausgabe nach /dev/null, dies mal auf einem 
schnelleren Rechner:

root@jq600l:/miras/entwick/listqc# time ./listqc2 8 2 25 75  > /dev/null
563853888 Kombinationen mit 595752418 Rekursionen gefunden

real  1m34,071s
user  1m33,338s
sys  0m0,721s

root@jq600l:/miras/entwick/listqc# time ./listqc-tre2 8 2 25 75  > 
/dev/null
563853888 Kombinationen mit 1450916065 Rekursionen gefunden

real  6m37,411s
user  6m36,493s
sys  0m0,876s

Bei 563 Millionen Ergebnissen ist das schon eine kleine Kaffeepause 
Unterschied.

> Ich fand das bei projecteuler manchmal so krass, wenn ich nach 3 Tagen
> mit riesigem Aufwand das Ergebnis geradeso rausbekommen habe, und im
> Forum postet dann jemand einen 5-Zeiler der mehrere Größenordnungen
> schneller ist.

Wenn ich irgendwann mal wieder mehr Zeit habe, könnte es mich auch 
interessieren. Bei dieser Aufgabe hier hat es mich einfach gepackt, 
praktische Erfahrungen zu machen, statt nur herum zu theoretisieren.

[Yalu X. (yalu) (Moderator)]

Hab auch mal was gebastelt (s. Anhang).

Hier sind die Zeiten im Vergleich, gemessen auf einem i5-6267U mit 2,90
GHz.

Ohne Ausgabe:

$ time ./listqc2 8 2 25 75 o
563853888 Kombinationen mit 595752418 Rekursionen gefunden 

real    0m22.185s
user    0m22.158s
sys     0m0.003s


$ time ./listqc-tre2 8 2 25 75 o
563853888 Kombinationen mit 1450916065 Rekursionen gefunden 

real    0m10.024s
user    0m10.018s
sys     0m0.000s


$ time ./listqc-yalu 8 2 25 75 o
563853888 Kombinationen gefunden

real    0m3.566s
user    0m3.559s
sys     0m0.004s

Mit Ausgabe in /dev/null:

$ time ./listqc-tre2 8 2 25 75 > /dev/null
563853888 Kombinationen mit 1450916065 Rekursionen gefunden 

real    5m10.864s
user    5m9.613s
sys     0m1.003s


$ time ./listqc2 8 2 25 75 > /dev/null
563853888 Kombinationen mit 595752418 Rekursionen gefunden 

real    1m18.681s
user    1m17.900s
sys     0m0.727s


$ time ./listqc-yalu 8 2 25 75 > /dev/null 
563853888 Kombinationen gefunden

real    0m29.787s
user    0m28.786s
sys     0m0.980s

[Tilo R. (joey5337)]

Jobst Q. schrieb:
> Aber Optimierungsbedarf hat dein Programm bei der Ausgabe.

:-)
Auf jeden Fall. Ich habe die Ausgabe nur genutzt um das Ergebnis zu 
diffen, die Performance habe ich nicht mal getestet.
Yalus' Version sieht da ziemlich optimal aus.

Auch sein pruning spart nochmal einen Faktor 2 bis 3 an 
Rekursionsaufrufen.
Ich glaube nicht, dass die Tiefensuche jetzt noch weiter verbessert 
werden kann.

[Jobst Q. (joquis)]

Tilo R. schrieb:
> Yalus' Version sieht da ziemlich optimal aus.

Sehe ich auch auch so. Also kann ich mich von der Aufgabe verabschieden.

[michael_ (Gast)]

Erik schrieb:
> In meinem realem Problem ist das nicht fest definiert, ich benötige
> einen generischen Algorithmus der mit den 4 Parametern:
> - Anzahl Felder
> - gewünsche Summe
> - kleinstmögliche Zahl (ist in reality meist 2 oder 3, muss größer als 0
> sein)
> - größtmögliche Zahl (ist meist im Rahmen von 20 bis 30 kann aber auch
> größer sein)

Nennt man eine Reihe.
Aber da du mit Mathe nichts im Sinn hast, kannst du das auch nicht 
lösen.

[TotoMitHarry (Gast)]

Yalu X. schrieb:
> Hier sind die Zeiten im Vergleich, gemessen auf einem i5-6267U mit 2,90
> GHz.

Auch interessant, hier mal mit einem 2,4Ghz ARM (RK3588).

gcc

time ./test 8 2 25 75 o 
563853888 Kombinationen gefunden

real  0m5,894s
user  0m5,873s
sys  0m0,020s


gcc -O1

time ./test 8 2 25 75 o 
563853888 Kombinationen gefunden

real  0m3,217s
user  0m3,211s
sys  0m0,005s

time ./test 8 2 25 75 > /dev/null
563853888 Kombinationen gefunden

real  0m25,337s
user  0m24,594s
sys  0m0,737s