Das deutsche Python-Forum

@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

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

heiliga horsd hat geschrieben:@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...

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

BlackJack hat geschrieben: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

Vorerst wohl die letzte Variante von mir — jetzt parallelisiert.
lotto_04.py:

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from functools import partial
from itertools import combinations, islice
from multiprocessing import cpu_count, Pool
from operator import add, 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, 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 count_sums(length, start):
    histogram = [0] * (MAX_SUM + 1)
    for combination in islice(lotto_combinations(start), length):
        histogram[sum(combination)] += 1
    return histogram


def search_combination(sum_histogram, length, start):
    result = list()
    for combination in islice(lotto_combinations(start), length):
        the_sum = sum(combination)
        x = the_sum * sum_histogram[the_sum]
        if x >= 2000000 and product(combination) == x:
            result.append(tuple(combination))
    return result


def main():
    combinatio_count = number_of_combinations(N, K)
    chunksize = (combinatio_count // cpu_count()) + 1
    offsets = range(0, combinatio_count, chunksize)
    
    pool = Pool()
    
    sum_histogram = [0] * (MAX_SUM + 1)
    for histogram in pool.map(partial(count_sums, chunksize), offsets, 1):
        sum_histogram = map(add, sum_histogram, histogram)
    
    for combinations in pool.map(
        partial(search_combination, sum_histogram, chunksize), offsets, 1
    ):
        for combination in combinations:
            print combination


if __name__ == '__main__':
    main()

Ist damit die schnellste Python-Version von mir, wenn man es mit PyPy ausführt. Noch einmal ≈19% schneller als die bisher schnellste sequentielle Variante mit PyPy.

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_02.py     python  6m41.216s        -7.24
lotto_03.py     python  1m10.051s        -2.05
lotto_04.py     python    39.093s        -1.14 (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
lotto_04.py     pypy       8.219s         4.15 (Neu)
lotto_02.c                 1.316s        25.95
lotto_01.c                 0.267s       127.88

Hallo,

entschuldigung für die späte Antwort, habe grade wenig Zeit...

Hab die Lösung mal durch PyPy gejagt, ist jetzt nach 2 Sekunden durch.... aber ich schätze mal wirklich noch schneller schafft mans mit Python wohl wirklich nicht.

Gruß heiliga horsd

So, hab mir jetzt den Code nochmal angeschaut und mir die Messergebnisse mal durch den Kopf gehen lassen. Ich frage mich gerade, warum Lotto04.py (Parallelisiert) mit CPython langsamer ist als Lotto01.py (Sequentiell), mit PyPy der Sachverhalt jedoch genau anders herum ist?

@heiliga horsd: Weil in der 4er Variante der Kombinationsgenerator in Python geschieben ist und das ist selbst parallelisiert langsamer als `itertools.combinations()` was in CPython in C implementiert ist. Bei PyPy macht es keinen Unterschied ob man `itertools.combinations()` oder die in Python geschriebene Generatorfunktion verwendet. Das war bei mir die 3er Variante. Da ist PyPy bei der 1er und der 3er ungefähr gleich schnell, aber CPython bei der 3er *deutlich* langsamer.

Noch mal zwei Datenpunkte für einen Raspberry Pi (mit Raspbian als Betriebssystem): ``lotto_01.py`` hat 11 Minuten und 16 Sekunden gebraucht und ``lotto_01.c`` war in knapp unter 2s fertig.

Das deutsche Python-Forum

Nicht nachvollziehbares Verhalten von itertools.combinations

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat

Re: Nicht nachvollziehbares Verhalten von itertools.combinat