Nicht nachvollziehbares Verhalten von itertools.combinations

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
heiliga horsd

Dienstag 19. Juni 2012, 13:43

Hallo,

habe mich mal dahinter gesetzt, folgendes Rätsel zu lösen:

Peter träumte wieder einmal vom großen Geld. Er stellte sich gerade vor, sechs richtige im Lotto zu haben, als es plötzlich hell aufblitzte. Eine Märchenfee stand vor ihm und sagte: "Du hast einen Wunsch frei."

Ohne zu zögern reichte Peter ihr ein Stück Papier und einen Stift. "Wie wär's, wenn du mir die Lottozahlen von nächster Woche hier aufnotierst?", meinte er. "Alle sechs Lottozahlen.", sagte die Fee erstaunt, "Das sind ja gleich sechs Wünsche auf einmal, also das geht nun wirklich nicht." Dennoch notierte die Fee eine Zahl auf dem Zettel und sagte: "Wenn du alle sechs Lottozahlen von nächster Woche zusammenaddierst, dann kommst du auf dieses Ergebnis!"

Peter sah sich die Zahl an und überlegte. "Oh Gott, da gibt es sicher tausende Möglichkeiten mit sechs verschiedenen Zahlen zwischen 1 und 49 auf diese Summe zu kommen", meinte er resigniert. "OK, ich geb' dir noch einen Tipp.", sagte die Fee, "Rechne doch mal genau aus, wieviele Möglichkeiten es gibt, die diese Summe ergeben. Wenn du das Ergebnis dann mit der Zahl malnimmst, die ich dir eben aufgeschrieben habe, 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."

Peter wollte sich gerade für den Tipp bedanken, als die Fee auch schon wieder verschwand. Nun begann er zu rechnen, und bei der nächsten Lottoziehung hatte er tatsächlich sechs Richtige. Welche sechs Zahlen wurden gezogen?

Nun habe ich mal ein bisschen rumgescripted und bin auf ein merkwürdiges Verhalten von itertools.combinations() gestoßen (Python 3):

Code: Alles auswählen

from itertools import combinations

def product(iterable):
    result = 1
    for element in iterable:
        result *= element
    return result

Summen = {}
Zahlen = [Zahl for Zahl in range(1,50)]
Kombinationen = combinations(Zahlen, 6)

def Häufigkeit_Bestimmen():
    for Eine_Kombination in Kombinationen:
        Summe_der_Zahlen = sum(Eine_Kombination)
        if Summe_der_Zahlen in Summen:
            Summen[Summe_der_Zahlen] += 1
        else:
            Summen[Summe_der_Zahlen] = 1
    return Summen

Summen = Häufigkeit_Bestimmen()

#for Eine_Kombination in Kombinationen:
#   Summe_der_Zahlen = sum(Eine_Kombination)
#    x = Summe_der_Zahlen * Summen[Summe_der_Zahlen]
#    if product(Eine_Kombination) == x and x > 2*10**6:
#        print(Eine_Kombination)

Kombinationen = combinations(Zahlen, 6)
for Eine_Kombination in Kombinationen:
    Summe_der_Zahlen = sum(Eine_Kombination)
    x = Summe_der_Zahlen * Summen[Summe_der_Zahlen]
    if product(Eine_Kombination) == x and x > 2*10**6:
        print(Eine_Kombination)
So wie es jetzt ist, ist es zwar leider nicht schön (gibt es Verschönerungsansätze abgesehen vom Englisch-Deutsch-Mischmasch?), funktioniert aber. Mich wundert, warum die auskommentierte Version nicht funktioniert, ich bekomme erst die richtige Lösung, wenn ich die Kombinationen neu erstelle. Warum?

Gruß HH
Benutzeravatar
Hyperion
Moderator
Beiträge: 7477
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Dienstag 19. Juni 2012, 13:50

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

Sobald Du einen einmal durchlaufen hast, ist dieser "aufgebraucht" und springt nicht "magisch" wieder auf den Anfang.

`itertools.tee` ist hier Dein Freund, wenn Du das Erstellen nur einmal formulieren willst.

Hier mal ein Beispiel in Python 2.7:

Code: Alles auswählen

>>> c = combinations("abc", 2)
>>> [item for item in c]
[('a', 'b'), ('a', 'c'), ('b', 'c')]
>>> [item for item in c]
[]
encoding_kapiert = all(verstehen(lesen(info)) for info in (Leonidas Folien, Blog, Folien & Text inkl. Python3, utf-8 everywhere))
assert encoding_kapiert
heiliga horsd

Dienstag 19. Juni 2012, 13:59

Ah OK, dass man Generatoren nur einmal verwenden kann wusst ich so nicht. Gibts auch keine Möglichkeit die nochmal schnell zu "erneuern"?

Ich hoffe ich habe deinen Hinweis mit itertools.tee (Danke dafür übrigens) richtig verstanden & umgesetzt:

Code: Alles auswählen

from itertools import combinations,tee

def product(iterable):
    result = 1
    for element in iterable:
        result *= element
    return result

Summen = {}
Zahlen = [Zahl for Zahl in range(1,50)]
Kombinationen = tee(combinations(Zahlen, 6))

def Häufigkeit_Bestimmen():
    for Eine_Kombination in Kombinationen[0]:
        Summe_der_Zahlen = sum(Eine_Kombination)
        if Summe_der_Zahlen in Summen:
            Summen[Summe_der_Zahlen] += 1
        else:
            Summen[Summe_der_Zahlen] = 1
    return Summen

Summen = Häufigkeit_Bestimmen()

for Eine_Kombination in Kombinationen[1]:
    Summe_der_Zahlen = sum(Eine_Kombination)
    x = Summe_der_Zahlen * Summen[Summe_der_Zahlen]
    if product(Eine_Kombination) == x and x > 2*10**6:
        print(Eine_Kombination)
Einziges Problem hierbei ist kurzzeitiger RAMverbrauch-Anstieg um mehr als 1 GB... :(
EyDu
User
Beiträge: 4872
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Dienstag 19. Juni 2012, 14:06

Auch sonst gibt es da noch einiges zu verbessern. Als erstes fallen natürlich die Namensgebung und der Style auf. Halte dich bitte an PEP 8, dein Code ist wirklich unglaublich schwer zu lesen. Und sachen wie ``eine_kombination in kombinationen`` ist auch redundant. Warum nicht einfach ``for kombination in kombinationen`` ? Hinzu kommte, das deine Namen nichts aussagen. "Summen", "Zahlen" und "Kombinationen" könnte alles mögliche sein. Natürlich ist das hier nur Code zum testen, aber du zeigst den Code anderen , welche diesen nachvollziehen sollen.

Auch lässt sich einiges kürzer schreiben. Deine product-Methode, lässt sich einfach mittels

Code: Alles auswählen

import operator

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

Deine Zahlen kannst du auch einfacher generieren:

Code: Alles auswählen

zahlen = list(range(1, 50))
Für "Summen" bietet sich der Counter aus dem collections-Modul an. Dann fällt die ganze Methode zusammen auf

Code: Alles auswählen

summe = collections.Counter(map(sum, kombinationen))
Statt map sollte man vielleicht besser imap aus dem itertools-Modul verwenden oder einen Generatorausdruck verwenden.
Das Leben ist wie ein Tennisball.
Benutzeravatar
/me
User
Beiträge: 3257
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Dienstag 19. Juni 2012, 14:15

heiliga horsd hat geschrieben:Einziges Problem hierbei ist kurzzeitiger RAMverbrauch-Anstieg um mehr als 1 GB... :(
Wie sagt die Dokumentation zu tee doch so schön: "This itertool may require significant auxiliary storage (depending on how much temporary data needs to be stored). In general, if one iterator uses most or all of the data before another iterator starts, it is faster to use list() instead of tee()".

Auf der anderen Seite ist die Frage, warum man vorhandenes RAM nicht benutzen wollen würde. Ein Computer wird nicht dadurch schneller, dass er möglichst viel freies RAM hat.
Benutzeravatar
/me
User
Beiträge: 3257
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Dienstag 19. Juni 2012, 14:18

EyDu hat geschrieben:

Code: Alles auswählen

import operator

def product(iterable):
    return reduce(operator.mul, iterable, 1)
In Python 3 ist reduce meines Wissens nach in das functools-Modul gewandert.

Code: Alles auswählen

import functools
import operator

def product(iterable):
    return functools.reduce(operator.mul, iterable, 1)
In Python 2.7 geht das übrigens auch schon und macht dann den Umstieg leichter.
deets

Dienstag 19. Juni 2012, 14:23

heiliga horsd hat geschrieben:Ah OK, dass man Generatoren nur einmal verwenden kann wusst ich so nicht. Gibts auch keine Möglichkeit die nochmal schnell zu "erneuern"?
Wie denn, wenn er zb von der Zeit abhaengige Daten produziert, oder zufaellige, oder oder oder.... das ist Code der eben nur einmal ausgefuehrt werden kann. Entweder speicherst du zwischen, oder du reichst generator-generatoren rum, d.h. du selbst schaffst dir eine Moeglichkeit, die immer wieder zu generieren.
heiliga horsd

Dienstag 19. Juni 2012, 14:27

Danke für die Antworten!

@EyDu: Ja das mit den Namen war mir schon vorher bewusst, werd ich vermutlich noch ändern.

reduce und Counter kannte ich noch nich, Danke! da hat wohl Guidos Zeitmaschine wieder zugeschlagen...

@/me: Das stimmt. Ich persönlich habe jedoch lieber etwas zu viel RAM frei als zu viel auf der FP ausgelagert.
Habe reduce schon gefunden, trotzdem nochmals Danke für den Hinweis, musste jedoch auch erst googlen um es zu finden.

@deets: Daran hatte ich nicht gedacht :oops:

Code: Alles auswählen

from itertools import combinations,tee
from functools import reduce
import operator
import collections

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

Zahlen = list(range(1,50))
Kombinationen = tee(combinations(Zahlen, 6))

Summen = collections.Counter(map(sum, Kombinationen[0]))

for Eine_Kombination in Kombinationen[1]:
    Summe_der_Zahlen = sum(Eine_Kombination)
    x = Summe_der_Zahlen * Summen[Summe_der_Zahlen]
    if product(Eine_Kombination) == x and x > 2*10**6:
        print(Eine_Kombination)
        
Das wäre jetzt meine Endgültige Lösung, das Namensproblem mal außer Acht gelassen.
EyDu
User
Beiträge: 4872
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Dienstag 19. Juni 2012, 14:37

In diesem Fall brauchst du eigentlich gar kein tee, da beim Erzeugen des Summen die komplette Liste im Speicher abgelegt werden muss. Du könntest also statt des tee-Aufrufs gleich list verwenden oder, deutlich speicherschonender, den Generator einfach doppelt erstellen:

Code: Alles auswählen

Summen = collections.Counter(map(sum, combinations(Zahlen, 6))

for Eine_Kombination in combinations(Zahlen, 6):
    ....
Da du bereits Python 3.x verwendest, muss der map-Aufruf auch nicht in itertools.imap geändert werden.

Edit: Auch wenn die Geschwindigkeit wohl nicht so ins Gewicht fällt, ich würde die Bedingungen des letzten ifs vertauschen und den Grenzwert auslagern. Letzteres vorallem, da es sich so oder so um eine Konstante handelt, die durch einen Namen etwas weniger magisch wird.

Code: Alles auswählen

MIN_VALUE = 2*10**6
if x > MIN_VALUE and product(Eine_Kombination) == x:
Das Leben ist wie ein Tennisball.
Benutzeravatar
/me
User
Beiträge: 3257
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

Dienstag 19. Juni 2012, 15:04

EyDu hat geschrieben:Edit: Auch wenn die Geschwindigkeit wohl nicht so ins Gewicht fällt, ich würde die Bedingungen des letzten ifs vertauschen und den Grenzwert auslagern.
Wenn Geschwindigkeit spannend wird, dann würde ich PyPy verwenden. Auf meinem Rechner braucht das nur 25% der Zeit.
heiliga horsd

Mittwoch 20. Juni 2012, 17:59

Hab ein bisschen mit der Generator-Generato-Idee gespielt, wusste jetzt aber nicht wie ich die dann sinnvoll ansprechen kann ohne die Generatoren selber wieder in einer Liste zu speichern (was man ja mit einer List-Comprehension schneller machen könnte?)

Code: Alles auswählen

def give_combinations(iterable, n):
    if n > 0:
        for number in range(0, n):
            yield combinations(NUMBERS, 6)
    else:
        raise ValueError

COMBINATIONS = give_combinations(NUMBERS, 2)

Code: Alles auswählen

from itertools import combinations
from functools import reduce
import operator
import collections

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

NUMBERS = list(range(1,50))
MIN_VALUE = 2*10**6

Sums = collections.Counter(map(sum, combinations(NUMBERS, 6)))

for combination in combinations(NUMBERS, 6):
    sum_of_numbers = sum(combination)
    x = sum_of_numbers * Sums[sum_of_numbers]
    if x > MIN_VALUE and product(combination) == x:
        print(combination)
Ich hoffe das sieht aus PEP8-Sicht besser aus?

Bzgl. Geschwindigkeit:
Pypy unterstützt ja leider kein Python 3.
Insgesamt läuft mein Programm (Pi mal Daumen mit der Armbanduhr "gemessen") ~39 Sekunden, nach ~23 Sekunden wird meine Lösung gefunden. Evtl. könnte man die knapp 14 Millionen Ergebnisse in Divide & Conquer-Manier aufteilen und von verschiedenen Threads absuchen lassen? Aber ob man da so viel raus holt weiß ich auch nicht, dafür hab ich in dem Bereich viel zu wenig Ahnung...

Gruß heiliga_horsd


P.S.: Super Support hier, sollte mal wieder erwähnt werden!
EyDu
User
Beiträge: 4872
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Mittwoch 20. Juni 2012, 19:19

Die Generatoren in einer Liste zu halten ist schon in Ordnung. Es ging mir darum, dass du nicht die Ergebnisse eines Iteratordurchlaufs in einer Liste speicherst. Das passiert hier, wenn du tee verwendest. Ich würde deine Funktion eifach so schreiben:

Code: Alles auswählen

def give_combinations():
    return combinations(NUMBERS, 6)
Überall wo du nun ``combinations(NUMBERS, 6)`` stehen hast, ersetzt du das einfach durch den Aufruf der Funktion. Damit hast du die gleichen Parameter ausgelagert. Die 50 (bzw. die 49 und dan beim Erzeugen der Nummern 1 addieren) würde ich noch in eine Konstante auslagern, ebenfalls die 6. Nach PEP 8 sollte es außerdem noch ``sums`` und nicht ``Sums`` heißen. Die Konstanten würde ich hinter die Importe setzen und vor die ersten Funktionsdefinitionen. Außerdem sollte der Code auf Modulebene noch in eine main-Funktion, damit man das Modul auch importieren kann:

Code: Alles auswählen

def main():
    sums = collections.Counter(...)
    ...

if __name__ == "__main__":
    main()
Das sind aber nur Kleinigkeiten, im Allgemeinen sieht das Programm doch sehr gut aus.

Edit: Zur Parallelisierung: Das sollte mit der for-Schleife gut und relativ einfach machbar sein. Zum Einstieg vielleicht gar keine schlechte Problemstellung. Schau dir dazu mal das multiprocessing Modul an, dann hast du, im Gegensatz zu Threads unter CPython, auch richtige Nebenläufigkeit. Mit etwas Geschick könntest du auch die Berechnung von ``Sums`` entsprechend umstellen.
Das Leben ist wie ein Tennisball.
heiliga horsd

Mittwoch 20. Juni 2012, 19:34

Das mit der Main-Fkt. hatte ich ganz vergessen, Danke für den Hinweis.

Code: Alles auswählen

from itertools import combinations
from functools import reduce
import operator
import collections

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

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

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

def main():
    sums = collections.Counter(map(sum, give_combinations()))
    for combination in give_combinations():
        sum_of_numbers = sum(combination)
        x = sum_of_numbers * sums[sum_of_numbers]
        if x > MIN_VALUE and product(combination) == x:
            print(combination)
        
if __name__ == "__main__":
    main()
(Bliebe nur noch die Frage nach der Geschwindigkeitsoptimierung/Parallelisierbarkeit. Kann aber auch mit der aktuellen Laufzeit leben.)
Sorry habe deinen Edit zu spät gesehen... Danke für den Modulhinweis. Werd mich morgen mal ein wenig damit herumspielen :)

Gruß HH
BlackJack

Mittwoch 20. Juni 2012, 21:59

Auf dem PC ist es in C richtig schnell, aber auf dem C64 reicht es leider nicht. Das Programm läuft nun schon eine Stunde und hat noch kein Ergebnis ausgespuckt. Hier der Quelltext:

Code: Alles auswählen

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

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

static uint8_t combination[K];
static uint32_t sum_counts[MAX_SUM];

void combination_init(void)
{
    uint8_t i;
    for (i = 0; i < K; ++i) {
        combination[i] = i + 1;
    }
}

_Bool combination_next(void)
{
    int8_t i;
    uint8_t n = N;
    
    for (i = K - 1; i >= 0; --i, --n) {
        ++combination[i];
        if (combination[i] <= n) break;
    }
    ++i;
    if (combination[i] > n) {
        if (i == 0) return false;
        for (i = i; i < K; ++i) {
            combination[i] = combination[i - 1] + 1;
        }
    }
    return true;
}

uint16_t combination_sum(void)
{
    uint8_t i;
    uint16_t result = 0;
    
    for (i = 0; i < K; ++i) {
        result += combination[i];
    }
    
    return result;
}

uint32_t combination_product(void)
{
    uint8_t i;
    uint32_t result = 1;
    
    for (i = 0; i < K; ++i) {
        result *= combination[i];
    }
    
    return result;
}

void combination_print(void)
{
    uint8_t i;
    
    for (i = 0; i < K; ++i) {
        printf("%2d ", combination[i]);
    }
    puts("");
}

void calculate_sum_counts(void)
{
    memset(sum_counts, 0, sizeof(sum_counts));
    combination_init();
    do {
        ++sum_counts[combination_sum()];
    } while(combination_next());
}

void search_combination(void)
{
    uint16_t sum;
    uint32_t x;
    
    combination_init();
    do {
        sum = combination_sum();
        x = sum * sum_counts[sum];
        if (x > 2000000 && x == combination_product()) {
            combination_print();
        }
    } while(combination_next());
}

int main(void)
{
    calculate_sum_counts();
    search_combination();
    return 0;
}
Laufzeit auf dem PC <0,5s.
Benutzeravatar
snafu
User
Beiträge: 5901
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Donnerstag 21. Juni 2012, 01:53

@heiliga horsd: Mach mal aus deiner `main()`-Funktion etwas wie `find_combination()` und aus dem `print()` am Ende der Funktion ein `return`. Du kannst ja aufhören, sobald du eine passende Zahlenfolge gefunden hast, da es laut Fee nur eine einzige korrekte Lösung gibt und das ganze erspart dir etliche Sekunden an Laufzeit. Das Ergebnis von `find_combination()` lässt sich dann natürlich wieder in einer `main()`-Funktion anzeigen.

EDIT: Und nicht zu vergessen natürlich die Verwendung von `imap()` beim Zählen der Summen. Das drückt die Laufzeit auf meinem Laptop mit PyPy von ~12s auf ~11s. Möglicher Kompatibilitätscode bei den Import-Anweisungen, damit möglichst viele Python-Versionen funktionieren:

Code: Alles auswählen

try:
    from itertools import imap
except ImportError:
    imap = map
Und innerhalb der Funktion halt noch das `map()` in `imap()` ändern.

Und ja, ich hab mitgekriegt, dass du Python 3 verwendest. Trotzdem ist das ganz nett für andere Mitlesende bzw für dich, falls du dein Snippet irgendwann doch mal mit ner anderen Python-Version ausführen willst.
Antworten