Nicht nachvollziehbares Verhalten von itertools.combinations

[heiliga horsd]

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

[Hyperion]

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]
[]

[heiliga horsd]

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]

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.

[/me]

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.

[/me]

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]

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]

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

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]

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:

[/me]

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]

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]

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.

[heiliga horsd]

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]

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.

[snafu]

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

[heiliga horsd]

Code: Alles auswählen

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

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

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

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

def check_combinations(combinations_to_check):
    for combination in combinations_to_check():
        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(check_combinations, give_combinations(), CHUNKSIZE)
    return result
        
if __name__ == "__main__":
   print(find_combination())

Leider kann ich mit der Fehlermeldung nicht viel anfangen, da ich keine Ahnung habe, welches Tupel da gemeint ist.

Code: Alles auswählen

Traceback (most recent call last):
  File "C:\Users\XX\Desktop\Lotto.py", line 41, in <module>
    print(find_combination())
  File "C:\Users\XX\Desktop\Lotto.py", line 37, in find_combination
    result = pool.map(check_combinations, give_combinations(), CHUNKSIZE)
  File "C:\Python32\lib\multiprocessing\pool.py", line 251, in map
    return self.map_async(func, iterable, chunksize).get()
  File "C:\Python32\lib\multiprocessing\pool.py", line 556, in get
    raise self._value
TypeError: 'tuple' object is not callable

Ansonsten hoffe ich, dass mein Ansatz nicht allzu verkehrt ist.

Gruß HH

[BlackJack]

@heiliga horsd: `map()` wendet die Funktion in Argument 1 auf die *Elemente* von Argument 2 an, also auf jedes einzelne Tupel das ``give_combinations()`` liefert. Und das erste was Dein `check_combinations()` macht ist das Argument aufrufen. Das geht bei Tupeln nicht.

[BlackJack]

Ich habe mal bei folgender Python-Implementierung (für 2.6 — darum kein `collections.Counter`) mit CPython und PyPy die Zeit gemessen:

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(int)
    for combination in lotto_combinations():
        sum2count[sum(combination)] += 1
    
    for combination in lotto_combinations():
        the_sum = sum(combination)
        x = the_sum * sum2count[the_sum]
        if x >= 2000000 and product(combination) == x:
            print combination


if __name__ == '__main__':
    main()

Und dazu noch die C-Lösung mit folgender, etwas aufgeräumterer `combination_next()`:

Code: Alles auswählen

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

Ergebnis:

Code: Alles auswählen

Filename        Impl.   Runtime         Factor
==============  ======  =========  ===========
lotto_01.py     python    34.144s         1.00
lotto_01.py     pypy      11.635s         2.93
lotto_01.c                 0.267s       127.88

Ohne etwas am Python-Quelltext zu ändern ist PyPy fast 3× schneller. Und wenn man sich die Mühe macht es in C nach zu implementieren ist der Faktor 127.

Für algorithmische Verbesserungen stellt sich die Frage ob es möglich ist die Anzahl der Kombinationen, welche eine vorgegebene Summe ergeben, effizienter zu Zählen als tatsächlich all die Kombinationen zu generieren (für die erste Schleife); und ob es dann einen effizienten Weg gibt all die Kombinationen für eine Summe zu generieren, ohne *alle* Kombinationen zu generieren (für die zweite Schleife).

@heiliga horsd: Ich denke die `Pool.map()`-Varianten bringen nicht viel solange der Hauptprozess weiterhin alle ≈14M Kombinationen generiert und diese serialisiert an die Prozesse übermittelt um für jede Kombination ein Ergebnis zurück geschickt zu bekommen. Das dürften mehrere hundert Megabyte an Daten werden, die (de)serialisiert und zwischen den Prozessen hin und her übermittelt werden.

Wenn man das parallelisieren möchte, müssten man auch die Generierung der Kombinationen verteilen können, also beim Generieren der Kombinationen auch bei der x. Kombination beginnen können. Dann könnte man sowohl das Berechnen der Summenhäufigkeit, als auch das Testen aller Kombinationen verteilen. Bei zwei Prozessen könnte einer dann zum Beispiel die ersten ≈7M Kombinationen testen und der andere die zweiten ≈7M Kombinationen. `itertools.combinations()` kann aber nur von vorne aufzählen. Man müsste sich also einen eigenen Kombinations-Iterator schreiben und neben der Funktion, welche die lexikografisch nächste Kombination aus einer gegebenen Kombination erzeugt, auch eine welche die x. lexikographische Kombination aus einem gegebenen x erzeugt. Sollte beides machbar sein. Vorlage für das generieren könnten die Funktionen `combination_init()` und `combination_next()` aus meinem C-Programm sein. Fehlt also nur noch die Funktion um aus x die zugehörige Startkombination zu berechnen. Und dann muss das in Python-Code parallel ausgeführt nur noch schneller sein als der C-Code hinter `itertools.combinations()` sequentiell ausgeführt.

[heiliga horsd]

Komme dir bei deinem ersten Post nicht ganz hinterher - wieso kann ich Tupel nicht aufrufen?

Code: Alles auswählen

>>> a = (1,2,3)
>>> sum(a)
6

bzw.

Code: Alles auswählen

>>> a = ((2,3,4),(3,4,5),(4,5,6))
>>> map(sum, a)
<map object at 0x0000000003123A58>
>>> for b in map(sum,a):
	print(b)

	
9
12
15
>>> 

Funktioniert doch auch, ich übergebe einer Funktion doch da ein Tupel? Oder wie meinst du das?

Für algorithmische Verbesserungen stellt sich die Frage ob es möglich ist die Anzahl der Kombinationen, welche eine vorgegebene Summe ergeben, effizienter zu Zählen als tatsächlich all die Kombinationen zu generieren (für die erste Schleife); und ob es dann einen effizienten Weg gibt all die Kombinationen für eine Summe zu generieren, ohne *alle* Kombinationen zu generieren (für die zweite Schleife).

Ich bin kein Mathematiker, d.h. die Antwort kann ich dir nicht geben.

Wenn man das parallelisieren möchte, müssten man auch die Generierung der Kombinationen verteilen können, also beim Generieren der Kombinationen auch bei der x. Kombination beginnen können. Dann könnte man sowohl das Berechnen der Summenhäufigkeit, als auch das Testen aller Kombinationen verteilen. Bei zwei Prozessen könnte einer dann zum Beispiel die ersten ≈7M Kombinationen testen und der andere die zweiten ≈7M Kombinationen. `itertools.combinations()` kann aber nur von vorne aufzählen. Man müsste sich also einen eigenen Kombinations-Iterator schreiben und neben der Funktion, welche die lexikografisch nächste Kombination aus einer gegebenen Kombination erzeugt, auch eine welche die x. lexikographische Kombination aus einem gegebenen x erzeugt. Sollte beides machbar sein. Vorlage für das generieren könnten die Funktionen `combination_init()` und `combination_next()` aus meinem C-Programm sein. Fehlt also nur noch die Funktion um aus x die zugehörige Startkombination zu berechnen. Und dann muss das in Python-Code parallel ausgeführt nur noch schneller sein als der C-Code hinter `itertools.combinations()` sequentiell ausgeführt.

Stellt sich mir natürlich die Frage, ob es der Aufwand Wert ist und wie ich der Funktion sage, wann sie aufhören die Kombinationen zu erzeugen.

[Hyperion]

- wieso kann ich Tupel nicht aufrufen?

Code: Alles auswählen

>>> a = (1,2,3)
>>> sum(a)
6

Funktioniert doch auch, ich übergebe einer Funktion doch da ein Tupel? Oder wie meinst du das?

Hier rufst Du aber eine Funktion `sum` auf und nicht den Tupel; das wäre `a()` - und das geht nicht