Nicht nachvollziehbares Verhalten von itertools.combinations

[Hyperion]

Die Fehlermeldung passt nicht zum Code!

Code: Alles auswählen

Traceback (most recent call last):
  File "./combi2.py", line 38, in <module>
    print(find_combination())
  File "./combi2.py", line 34, in find_combination
    result = map(check_combinations, give_combinations(), CHUNKSIZE)
TypeError: argument 3 to map() must support iteration

Der dritte Parameter ist doch hier sinnlos (und falsch!)

Lässt man den weg, so fehlt der Parameter `sums`. Du kannst das via `functools.partial` regeln:

Code: Alles auswählen

def check_combinations(combination, sums=None):
    ...

result = map(partial(check_combinations, sums=sums), give_combinations())

Und schreibe doch endlich mal den Code auf *eine* Python-Version um. Das kann man ja alles kaum noch lesen

Edit: Ok, die Fehlermeldungen zu Deinem Code unterscheiden sich zwischen Python2 und 3. Du verwendest also Python3, ich habe es mit Python2 getestet! Dann schreibe den Code doch auch entsprechend, damit das hier nicht zu einer Ratestunde wird

[EyDu]

Du verwendest also Python3, ich habe es mit Python2 getestet! Dann schreibe den Code doch auch entsprechend, damit das hier nicht zu einer Ratestunde wird

Ich möchte ja nichts sagen, aber die erst Antwort in diesem Thread lautet:

Das hat nichts mit Python3 zu tun, sondern liegt am Verhalten von Generatoren!

[Hyperion]

@EyDu: Das war gestern und ich hatte es nicht mehr im Kopf. Durch diesen Schrunz:

Code: Alles auswählen

try:
    from functools import reduce
except ImportError:
    pass
try:
    from itertools import imap
except ImportError:
    imap = map

war ich nun irgend wie auf Python2 fixiert k.A. wieso.

[snafu]

Irgendeine bessere Lösung als das stumpfe Ausprobieren zu finden, brennt mir auch schon die ganze Zeit unter den Nägeln. Da bin ich aber mathemäßig nict begabt genug, als dass ich da nen sinnvollen Ansatz finden würde.

Blöd ist auch, dass die Schleife zweimal in vollem Umfang durchlaufen werden muss. Aber auch das geht nicht anders, da man ja nunmal zuerst die Summen braucht. Mit Vorfilterung im ersten Durchlauf (z.B. hinsichtlich des Rausschmeißens von Kombinationen, deren Produkt weniger als 2 Mio ist) verschlechtert man erheblich die Laufzeit. Hatte da schon ein paar Dinge ausprobiert.

[snafu]

Und hinsichtlich des try-import-except-Import-Error Gefrickels: Ich hatte ihm ja den Vorschlag gemacht, damit möglichst viele Leute im Forum den Code ausprobieren können, ohne Zusatztools benutzen zu müssen. Schön sieht das natürlich nicht gerade aus. In einem "echten" Projekt würde ich für sowas auch eher ein Extra-Modul anlegen, welches versionsübergreifend die passende Funktion zurückgibt. Dann hat man den Kompatibilitätskram schön abstrahiert.

[heiliga horsd]

Jetzt bin ich verwirrt - soll ich das try-Zeug bei den Importen behalten oder nicht??

Das CHUNKSIZE hatte ich komplett vergessen, war noch ein Überbleibsel der Pool.map-Variante.

Mit dem partial hat auch alles funktioniert, jedoch ist der Code jetzt noch langsamer als die erste fertige Version bevor es ans "optimieren" ging. Das ganze nun parallel laufen lassen bringt meinen PC erstmal kurz an seine Leistungsgrenzen, lastet CPU und RAM fast komplett für mehrere Sekunden aus und spuckt mir dann nach ~35 Sekunden das Ergebnis aus - Insgesamt also "nur" 4 Sekunden schneller. Da das Ergebnis bereits eher gefunden wird, suche ich nun nach einer Möglichkeit alle Prozesse aus dem Pool abzuballern, sobald das Ergebnis gefunden wurde - würde Zeit & Strom sparen.
Hier der aktuelle Code (parallelisiert):

Code: Alles auswählen

from multiprocessing import Pool
from itertools import combinations
import operator
import collections
from functools import reduce, partial
try:
    from itertools import imap
except ImportError:
    imap = map

DIFFERENT_VALUES = 49
NUMBERS = list(range(1,DIFFERENT_VALUES + 1))
MIN_VALUE = 2*10**6
PROCESSES = 7
CHUNKSIZE = 2*10**6

def product(iterable):
    return reduce(operator.mul, iterable, 1)

def give_combinations():
    return combinations(NUMBERS, 6)

def check_combinations(combination, sums = None):
    sum_of_numbers = sum(combination)
    x = sum_of_numbers * sums[sum_of_numbers]
    if x > MIN_VALUE and product(combination) == x:
        return combination
            
def find_combination():
    pool = Pool(processes=PROCESSES)
    sums = collections.Counter(imap(sum, give_combinations()))
    result = pool.map(partial(check_combinations, sums=sums),give_combinations(),
                      chunksize=CHUNKSIZE)
    return result
        
if __name__ == "__main__":
    for element in set(find_combination()): #Set um die ~14M None's los zu werden
        print(element)

An die Vorschläge von Blackjack hab ich mich noch nicht gesetzt, hatte noch keine Zeit.

@snafu: Ich glaube genau das ist ja das Problem des Rätsels - Man kommt nur "zu Fuß" ans Ziel. Lasse mich aber gerne eines besseren belehren!

Gruß HH

[BlackJack]

@heiliga horsd: Das ist IMHO eine unsinnige Vorgehensweise. Bei dem `Pool.map()` wird für iterierbare Objekte die keine abfragbare Länge haben erst einmal eine Liste mit allen Elementen erstellt. Ist zumindest in der Implementierung in Python 2.6 so. An der Stelle hat man im Grunde schon „verloren”. Und dann werden nicht nur ≈14 Millionen Kombinationen an die Prozesse übertragen, sondern auch ≈14 Millionen Ergebnisse, die alle bis auf *einen* Wert `None` sind. Das ist eine unglaubliche Verschwendung. Die ganzen Kombinationen werden auch nur in *einem* Prozess erzeugt, statt dass das auch Parallel passiert.

Wie gesagt: Man braucht einen eigenen Kombinations-Generator der auch mitten drin „aufsetzen” kann, wenn man das vernünftig parallelisieren möchte. Dann kann man auch den ersten Schritt mit dem Histogramm in Teilhistogramme aufteilen die im Hauptprozess zusammengeführt werden.

Parallel 35s? Solange braucht bei mir die ganz normale Version mit den beiden Schleifen über alle Kombination. Und ich dachte ich hätte hier einen lahmen Rechner.

@snafu: Ich habe ja auch immer noch die Hoffnung, dass man intelligenter an die Sache heran gehen kann. Bin aber mathematisch auch zu untalentiert. Zum Beispiel müsste es auch für die Anzahl der Kombinationen die eine gegebene Summe x ausmachen eine zwar rekursive, aber letztendlich schnellere Funktion geben als alle Kombinationen zu generieren um sie zu zählen. Dann braucht man von den möglichen Summen auch nur die Hälfte berechnen, denn wenn man sich das Ergebnis mal anschaut, sieht man eine symmetrische Verteilung.

Ich hatte auch mal versucht beim zweiten Durchlauf die Kombinationen zu ignorieren wo das x schon zu klein ist. Dazu habe ich im Histogramm nicht die Kombinationen zu den Summen gezählt, sondern in Listen gesteckt. ``lotto_02.py``:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import defaultdict
from itertools import combinations
from operator import mul


def product(iterable):
    return reduce(mul, iterable, 1)


def lotto_combinations(n=49, m=6):
    return combinations(xrange(1, n + 1), m)


def main():
    sum2count = defaultdict(list)
    for combination in lotto_combinations():
        sum2count[sum(combination)].append(combination)
    
    for the_sum, combinations in sum2count.iteritems():
        x = the_sum * len(combinations)
        if x >= 2000000:
            for combination in combinations:
                if product(combination) == x:
                    print combination


if __name__ == '__main__':
    main()

Gaanz böse Falle. Es wird nicht einmal zu viel Speicher für diesen Rechner hier verbraucht, aber es dauert *eeewig*:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
lotto_01.py     python    34.144s         1.00
lotto_02.py     pypy      21.054s         1.62
lotto_01.py     pypy      11.635s         2.93
lotto_01.c                 0.267s       127.88

[heiliga horsd]

@heiliga horsd: Das ist IMHO eine unsinnige Vorgehensweise. Bei dem `Pool.map()` wird für iterierbare Objekte die keine abfragbare Länge haben erst einmal eine Liste mit allen Elementen erstellt. Ist zumindest in der Implementierung in Python 2.6 so. An der Stelle hat man im Grunde schon „verloren”. Und dann werden nicht nur ≈14 Millionen Kombinationen an die Prozesse übertragen, sondern auch ≈14 Millionen Ergebnisse, die alle bis auf *einen* Wert `None` sind. Das ist eine unglaubliche Verschwendung. Die ganzen Kombinationen werden auch nur in *einem* Prozess erzeugt, statt dass das auch Parallel passiert.

Naja bin ehrlich gesagt noch nicht dazu gekommen deinem Hinweis nachzugehen. Wobei ich mich frage, ob die None's nicht Referenz auf ein einziges Objekt sind - Man bräuchte ja nicht mehr als ein None-Objekt im Speicher oder? Und Referenzen auf ein Objekt machen das Ding dann ja auch nicht so fett.

Wie gesagt: Man braucht einen eigenen Kombinations-Generator der auch mitten drin „aufsetzen” kann, wenn man das vernünftig parallelisieren möchte. Dann kann man auch den ersten Schritt mit dem Histogramm in Teilhistogramme aufteilen die im Hauptprozess zusammengeführt werden.

Wenn ich mal Zeit finde arbeite ich mich da auch mal ein - wobei hier eine Frage meinerseits wäre, wie ich so einem Generator mitteile, wann er aufhören muss und gleichzeitig schon Generator 2 mitteilen kann, wo er starten muss, bevor Generator 1 fertig ist.

Parallel 35s? Solange braucht bei mir die ganz normale Version mit den beiden Schleifen über alle Kombination. Und ich dachte ich hätte hier einen lahmen Rechner.

Ja, das bei einem AMD FX-4100 (Quad Core, 3.6GHZ). Richtig bitter die Laufzeit...

[heiliga horsd]

Hab jetzt auch mal diese Lösung:

http://www.python-forum.de/viewtopic.ph ... 29#p223629

in PyPy rein gefüttert, war nach 4 Sekunden durch.

[snafu]

Hab jetzt auch mal diese Lösung:

http://www.python-forum.de/viewtopic.ph ... 29#p223629

in PyPy rein gefüttert, war nach 4 Sekunden durch.

Ich würd's jetzt einfach bei dieser Variante belassen. Ich glaub, die scheint das beste zu sein, das man Performance-mäßig mit Python hinkriegen kann...

[BlackJack]

@heiliga horsd: 14M Objektzeiger sind bei einem 32-Bit System auch 53 MiB. Aber ich mache mir da weniger Gedanken um den Speicher als um die Laufzeit diese grossen Listen zu erzeugen und zu serialisieren, zwischen den Prozessen zu übertragen, und wieder zu deserialisieren.

Wo so ein Generator aufhören muss, kann man ja von aussen zum Beispiel mit `itertools.islice()` bestimmen. Die interessante Frage ist eher der Algoritmus die x. lexikografische Kombination direkt aus einem gegebenen x zu erzeugen kann, damit man diesen Startpunkt hat. Das geht auf jeden Fall, ich kann mich da dunkel an eine Vorlesung zu dem Thema erinnern. Muss mal in meinen Unterlagen suchen.

Bei 4 Sekunden mit PyPy lohnt sich der Aufwand das zu parallelisieren ja eigentlich kaum noch.

Ich habe hier einen Athlon64 X2 (Dual Core, 2,7 Ghz) allerdings mit 32-Bit-Betriebssystem. Da dauert ein sehr ähnliches Programm 11.635s.

Meinen zweiten Ansatz — sich die Kombinationen im ersten Durchlauf zu den entsprechenden Summen zu merken um nur noch die im zweiten Durchlauf zu testen wo Summe mal Anzahl gross genug ist — habe ich auch mal in C probiert. Das hat zwar nicht so eine katastrophale Laufzeit wie der Python-Versuch, ist aber trotzdem ≈5× langsamer als der „brute force” Ansatz bei dem einfach zweimal alle Kombinationen generiert werden. Ich dachte ja es lag bei Python an den dynamisch wachsenden Listen und dass ich das Problem in C umgehen kann, in dem ich einmal ein entsprechend grosses Array mit allen Kombinationen + Listenzeiger erzeuge und im Histogram einen Zeiger auf eine Kombination zu jeder Summe speichere und die Kombinationen dann über ihre Zeiger eine verkettete Liste bilden. Das ist Konstanter Aufwand pro Kombination. Das bisschen verketten ist aber anscheinend deutlich teurer als einfach die Kombinationen noch einmal zu generieren.

lotto_02.c:

Code: Alles auswählen

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#define N       49
#define K       6
#define MAX_SUM (279 + 1)       /* = N + N-1 + N-2 + N-3 + N-4 + N-5 + 1*/

typedef struct Combination {
    uint8_t numbers[K];
    struct Combination *next;
} Combination;

typedef struct {
    uint32_t length;
    Combination *items;
} Combinations;

typedef struct {
    uint32_t count;
    Combination *head;
} HistogramEntry;

HistogramEntry histogram[MAX_SUM];
Combinations combinations;

uint32_t number_of_combinations(uint8_t n, uint8_t k)
{
    uint32_t result = 1;
    uint8_t i, max;
    
    max = (k < n - k) ? k : n - k;
    for (i = 0; i < max; ++i) {
        result = (result * (n - i)) / (i + 1);
    }
    
    return result;
}

void Combination_init(Combination *combination)
{
    uint8_t i;
    for (i = 0; i < K; ++i) {
        combination->numbers[i] = i + 1;
    }
    combination->next = NULL;
}

_Bool Combination_next(Combination *combination)
{
    int8_t i;
    uint8_t n;
    
    for (i = K - 1, n = N - 1; i >= 0 && combination->numbers[i] > n; --i, --n);
    if (i < 0) return false;
    ++combination->numbers[i];
    for (i = ++i; i < K; ++i) {
        combination->numbers[i] = combination->numbers[i - 1] + 1;
    }
    return true;
}

uint16_t Combination_sum(Combination *combination)
{
    uint8_t i;
    uint16_t result = 0;
    
    for (i = 0; i < K; ++i) {
        result += combination->numbers[i];
    }
    
    return result;
}

uint32_t Combination_product(Combination *combination)
{
    uint8_t i;
    uint32_t result = 1;
    
    for (i = 0; i < K; ++i) {
        result *= combination->numbers[i];
    }
    
    return result;
}

void Combination_print(Combination *combination)
{
    uint8_t i;
    
    for (i = 0; i < K; ++i) {
        printf("%2d ", combination->numbers[i]);
    }
    putchar('\n');
}

void Combinations_init(void)
{
    uint32_t i;
    Combination combination;
    
    combinations.length = number_of_combinations(N, K);
    combinations.items = malloc(
        combinations.length * sizeof(*combinations.items)
    );
    i = 0;
    Combination_init(&combination);
    do {
        memcpy(&combinations.items[i++], &combination, sizeof(combination));
    } while(Combination_next(&combination));
    assert(i == combinations.length);
}

void Combinations_destroy(void)
{
    combinations.length = 0;
    free(combinations.items);
}

void calculate_histogram()
{
    Combination *combination;
    HistogramEntry *entry;
    uint32_t i;
    
    memset(histogram, 0, sizeof(histogram));
    
    for (
        i = 0, combination = combinations.items;
        i < combinations.length;
        ++i, ++combination
    ) {
        entry = &histogram[Combination_sum(combination)];
        ++entry->count;
        combination->next = entry->head;
        entry->head = combination;
    }
}

void search_combination(void)
{
    Combination *combination;
    uint16_t i;
    uint32_t x;
    
    for (i = 0; i < MAX_SUM; ++i) {
        x = i * histogram[i].count;
        if (x > 2000000) {
            combination = histogram[i].head;
            while (combination) {
                if (x == Combination_product(combination)) {
                    Combination_print(combination);
                }
                combination = combination->next;
            }
        }
    }
}

int main(void)
{
    Combinations_init();
    calculate_histogram();
    search_combination();
    Combinations_destroy();
    return 0;
}

Damit sieht der Stand meiner Versuche so aus:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
lotto_01.py     python    34.144s         1.00
lotto_02.py     pypy      21.054s         1.62
lotto_01.py     pypy      11.635s         2.93
lotto_02.c                 1.316s        25.95  (Neu)
lotto_01.c                 0.267s       127.88

@snafu: Wenn da nicht der Forscherdrang wäre. Bei meiner lahmen Kiste sind es immerhin noch ≈11s. Und auf dem C64 dauert das erste Aufzählen schon mehr als eine Stunde (da habe ich abgebrochen). Wäre schon schön wenn man das besser hinbekommen würde.

[heiliga horsd]

http://www.matheforum.net/read?i=899025

http://de.wikipedia.org/wiki/Stirling-Z ... weiter_Art

Hab mich da noch nicht weiter eingelesen, sollte nur mal als Hinweis für alle dienen, dass es da anscheinend tatsächlich einen mathematischen Weg gibt.

[snafu]

Man sollte vielleicht überlegen, welche Teilannahmen man treffen kann. Zum Beispiel weiß ich, dass jede Kombination, die (1, 2, 3, 4, 5) enthält und durch eine beliebige übrige Zahl (also von 6-49) ergänzt wird, als Produkt niemals größer als 2 Mio sein kann. Das Maximal mögliche Ergebnis ist 5880 für 1*2*3*4*5*49, ähnliches gilt für 2*3*4*5*6*49. Ich weiß nicht, inwiefern das erweiterbar ist, ohne "logische Fehler" einzubauen. Falls er klappt, könnte man am Ende eine Formel daraus machen. Ist aber erstmal nur ein Gedanke...

[snafu]

@heiliga horsd: Vielleicht am Rande nochmal zum Generator-Verhalten, sofern dir das bisher nicht ganz klar geworden ist: So ein Generator-Objekt ist ja im Grunde nicht viel mehr als eine Zustandmaschine, die auf Anforderung den jeweils nächsten Zustand berechnet und diesen zurückgibt. Es werden in deinem Anwendungsfall also nicht irgendwo (meinetwegen in einem C-Array) alle Kombinationen gespeichert und nur einzeln ausgespuckt, sondern die nächste Kombination steht wirklich erst dann fest, wenn sie "an der Reihe" ist. Und der Generator merkt sich zuvor zurückgelieferte Kombinationen auch nicht.

Durch dieses Verhalten können Generatoren potenziell Milliarden von Elementen zurückgeben (sogar unendlich viele), ohne dass es irgendwelche negativen Effekte auf den Speicherverbrauch hat. Das Problem fängt erst dann an, wenn man selber die Ausgaben z.B. in einer Liste sammelt. Generatoren sind also grundsätzlich eher dazu gedacht, dass ihre zurückgelieferten Elemente sofort verarbeitet werden und nicht erst in irgendeinem Container abgelegt werden.

Wie du dir jetzt vielleicht schon denken kannst, bringt es durch diesen Umstand nicht sondernlich viel, wenn Generatoren am Ende wieder von selbst auf den Ausgangszustand zurückspringen würden. Das hätte letztlich den selben Effekt wie das Erstellen eines neuen Generators, da jegliche Berechnung wieder von vorn beginnen müsste und sich auch wieder Schritt für Schritt weiter "tasten" müsste. Das ist ja auch der Grund, wieso man nicht nach Belieben an eine spätere Stelle im Generator springen kann, um möglicherweise tausende von vorherigen Elementen zu überspringen. Es geht technisch einfach nicht. Was natürlich ginge, wäre eine Option, die den Generator erst für eine spätere Stelle im Ablauf initialsiert, sodass er von dort an weitermachen kann. Dies bietet `itertools.combinations()` einem aber leider nicht an.

[BlackJack]

Ich habe jetzt `combinations_init()` und `combinations_next()` aus meinem C-Programm in einer Generator-Funktion in Python zusammengefasst. Und zusätzlich die Idee aus dem C-Programm übernommen das Histogramm in einer Liste und nicht in einem Wörterbuch zu speichern. Letzteres hat einen geringen Geschwindigkeitsvorteil weil direkt auf die Positionen zugegriffen werden kann, ohne das intern erst ein Hashwert benutzt werden muss.

Ausserdem kann die Generatorfunktion nicht nur mit der kleinsten lexikographischen Kombination beginnen, sondern an jeder beliebigen Position. Das verdanke ich dem Buch „Combinatorial Algorithms: Generation, Enumeration, and Search”, wo ich einen passenden Algorithmus gefunden habe (die `unrank()`-Funktion).

lotto_03.py:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from itertools import combinations
from operator import mul

N, K = 49, 6
MAX_SUM = sum(N - i for i in xrange(K))


def product(iterable):
    return reduce(mul, iterable, 1)


def number_of_combinations(n, k):
    if k > n or n < 0 or k < 0:
        return 0
    result = 1
    for i in xrange(min(k, n - k)):
        result = (result * (n - i)) / (i + 1)
    return result


def unrank(r, n=N, k=K):
    result = list()
    x = 1
    for i in xrange(1, k + 1):
        y = number_of_combinations(n - x, k - i)
        while y <= r:
            r -= y
            x += 1
            y = number_of_combinations(n - x, k - i)
        result.append(x)
        x += 1
    return result


def lotto_combinations(start=0, n=N, k=K):
    combination = unrank(start, n, k)
    while True:
        yield combination
        i = k - 1
        j = n - 1
        while i >= 0 and combination[i] > j:
            i -= 1
            j -= 1
        if i < 0:
            break
        combination[i] += 1
        for i in xrange(i + 1, k):
            combination[i] = combination[i - 1] + 1


def main():
    histogram = [0] * (MAX_SUM + 1)
    for combination in lotto_combinations():
        histogram[sum(combination)] += 1
    
    for combination in lotto_combinations():
        the_sum = sum(combination)
        x = the_sum * histogram[the_sum]
        if x >= 2000000 and product(combination) == x:
            print combination


if __name__ == '__main__':
    main()

Das ist in CPython ausgeführt jetzt erwartungsgemäss langsamer als mit dem in C implementierten `itertools.combinations()`. Aber nur um den Faktor ≈2 — ich hätte Schlimmeres erwartet. Besonders interessant finde ich aber, dass PyPy das genau so schnell, beziehungsweise sogar ein wenig schneller, ausführt als die erste Variante die noch `itertools.combinations()` verwendet hat! Da haben wir also einen Kombinationsgenerator in reinem Python der nicht langsamer ausgeführt wird als der in C geschriebene aus dem `itertools`-Modul. Cool.

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
lotto_03.py     python  1m10.051s        -2.05 (Neu)
lotto_01.py     python    34.144s         1.00
lotto_02.py     pypy      21.054s         1.62
lotto_01.py     pypy      11.635s         2.93
lotto_03.py     pypy      10.099s         3.38 (Neu)
lotto_02.c                 1.316s        25.95
lotto_01.c                 0.267s       127.88

Mit dem Quelltext hat man nun die Möglichkeit das Programm effizienter zu parallelisieren.

[heiliga horsd]

@snafu: Danke für die Generator-Erläuterung, mir hats schon ein bisschen gedämmert, jetzt hab ich das Schwarz auf Weiß
Wie man das mit den Produkten machen kann weiß ich so auch nicht. Frage mich auch gerade, ob es effizienter ist, paar Millionen Größenvergleiche anzustellen um sich das multiplizieren zu sparen oder eben gleich zu multiplizieren

@BlackJack: Ich hab das Gefühl du hast Gefallen an dem Problem gefunden
Da ich v.a. jetzt am WE Klausur- & Wetterbedingt wenig Zeit habe muss ich schauen wann ich zum testen und weiter probieren komme. Das mit dem unrank hört sich aber relativ cool an.

@all: Hat sich jemand das mit den Stirling-Zahlen angeschaut bzw. kennt sich damit aus? Bin da mit meinem 'begrenzten' Oberstufenwissen noch nicht auf dem mathematischen Level um da viel raus holen zu können... :K

[snafu]

@BlackJack: Kann ich bestätigen. Der in Python implementierte Kombinationsgenerator ist hier ein paar Zehntel Sekunden schneller als `itertools.combinations()`. Auch die Verwendung der Liste anstelle des Wörterbuchs ist schneller. PyPy ist echt der Hammer.

//edit: Wobei ja auch der verwendete Algorithmus aus deinem Buch recht effizient zu sein scheint, wenn man sich mal den Performance-Schub allein in CPython anguckt.

//edit2: Achso, jetzt schnall ich das. Nur `unrank()` ist aus dem Buch. Den Rest hattest du ja schon vorher. Und `unrank()` kommt erst dann wirklich ins Spiel, wenn ein wahlweiser Zugriff benötigt wird, d.h. Verändern des `start`-Parameters für den Kombinationsgenerator.

[snafu]

@all: Hat sich jemand das mit den Stirling-Zahlen angeschaut bzw. kennt sich damit aus? Bin da mit meinem 'begrenzten' Oberstufenwissen noch nicht auf dem mathematischen Level um da viel raus holen zu können... :K

Um ehrlich zu sein, ist mir bisher nicht klar geworden, wie der Stirling-Ansatz da überhaupt sinnvoll zu beitragen kann. Soweit ich weiß, hilft das eher bei Wahrscheinlichkeitsberechnungen. Evtl hat dich der Antwortende auch einfach nicht richtig verstanden...

[BlackJack]

@snafu: Bei Lotto geht es doch auch um Wahrscheinlichkeiten.

Bei Wahrscheinlichkeitsrechnung geht es oft um das Zählen von möglichen Ergebnissen mit bestimmten Eigenschaften. Wenn Du beantworten kannst wie gross die Wahrscheinlichkeit ist, dass bei einer Ziehung eine Kombination mit einer festen aber beliebigen Summe x kommt, dann weisst Du auch wie viele Kombinationen es für diese Summe gibt. Und umgekehrt.

[snafu]

Wenn Du beantworten kannst wie gross die Wahrscheinlichkeit ist, dass bei einer Ziehung eine Kombination mit einer festen aber beliebigen Summe x kommt, dann weisst Du auch wie viele Kombinationen es für diese Summe gibt. Und umgekehrt.

Nun ja, aber die konkrete Zahlenfolge finde ich damit ja trotzdem nicht heraus.

Übrigens hab ich die Idee, möglichst viele Zahlenfolgen vorab überspringen zu können, wieder aufgegriffen. Die Fee sagt ja: "[...] dann erhältst du eine sehr große Zahl von einigen Millionen, und diese Zahl kommt auch raus, wenn man alle sechs Lottozahlen miteinander malnimmt." Das heißt ja mit anderen Worten, alle Kombinationen, deren Produkt nicht mindestens 2 Mio ergibt, kommen gar nicht erst infrage.

So, jetzt verläuft die Erzeugung der Kombinationen ja nach einem bestimmten Muster. Man kann sich quasi einen Tacho denken, bei dem man mit dem Kilometerstand 123456 losfährt, wobei die Tachoeinheiten nicht von 0-9, sondern von 1-49 gehen. Wenn die am weitesten rechts stehende Einheit bei dem Maximalwert 49 angekommen ist, dann erhöht sich die links daneben stehende Einheit um eins. Im Gegensatz zu einer gewöhnlichen Tachoanzeige springt die rechte Einheit jedoch auf den Wert `linker_nachbar + 1`. Soll heißen: (1, 2, 3, 4, 5, 49) -> (1, 2, 3, 4, 6, 7) -> (1, 2, 3, 4, 6, 8) -> usw.

Da es dank `unrank()` nun wesentlich einfacher geworden ist, die Ergebnisse zu untersuchen, hab ich mal versucht, eine bestimmte "Tachozähler-Konstellation" zu bestimmen. Sieht noch etwas komisch aus, weil es keine Formel ist, aber vielleicht ein guter Anfang:

Code: Alles auswählen

>>>> unrank((49-6)+(49-6)+(48-6)+(47-6)+(46-6)+(45-6))
[1, 2, 3, 4, 10, 49]
>>>> unrank((49-6)+(49-6)+(48-6)+(47-6)+(46-6))
[1, 2, 3, 4, 9, 49]
>>>> unrank((49-6)+(49-6)+(48-6)+(47-6))
[1, 2, 3, 4, 8, 49]

Die zweite Tachoeinheit kann damit also mehr oder weniger gesteuert werden. Warum tu ich das? Nun, wenn sich die Tachoeinheiten jetzt nach und nach mit dem Maximalwert füllen würden, dann hat man ja beim Ermitteln des Produkts sozusagen auf der rechten Seite einen Faktor, welcher eine Potenz von 49 (bzw `N`) ist. Zur Veranschaulichung die Berechnung des Produkts:

Code: Alles auswählen

>>>> 1*2*3*4*5*49
5880
>>>> 1*2*3*4*49*49
57624
>>>> 1*2*3*49*49*49
705894
>>>> 1*2*49*49*49*49
11529602

Ich bleibe also bis 49^3 unter dem Minimalwert für das Produkt. Aufgrund des oben erläuterten Erzeugungsmusters ist auch garantiert, dass vorher kein "zu großes" Produkt herauskommen kann, womit man mindestens die bis zu dem Punkt theoretisch erzeugten Kombinationen unter den Tisch fallen lassen könnte, oder sehe ich das falsch?

Wie gesagt, da muss noch ein bißchen Form rein (ich will natürlich keinen endlos langen Term da stehen haben, sondern etwas hübsches mit Variablen) und so ganz zu Ende gedacht ist die Idee auch noch nicht. Aber an sich wage ich mal zu behaupten, dass man damit dem Ziel der reinen Berechnung des Ergebnisses schon ein Stück näher gekommen ist. Zumindest dürfte es schonmal die Zeit zum Durchprobieren merklich vermindern (also natürlich erst dann, wenn die Formel zum Erhalten des ersten Kandidaten komplett definiert ist).

//edit: Ups. Die 49 geht natürlich nur einmal pro Kombination. But you get the idea - perhaps. :D