Beste Funktion zum Ermittlen aller Summen gesucht!

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.
Antworten
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Freitag 18. Mai 2007, 14:05

Hallo!
Ich versuche grade einen Lösungsweg für eine Rätsel-Aufgabe zu finden, in der es um einen Stern geht, der aus 6 Linien besteht (2 Dreiecke). Nun soll man halt in jeden Knoten eine der Zahlen von 1 bis 12 eintragen, so dass die Summe jeder Linie 26 ergibt. Wenn einer einen Lösungsweg hat, nur her damit, auch wenns Offtopic ist...

Nun zu meiner Pythonfrage:
Um irgedwie an die Sache ranzugehen, wollte ich nach einigem Probieren erstmal alle Summen aus 4 Zahlen zwischen 1 und 12 ermitteln, die 26 ergeben.
Ich hab nun folgende Funktion dazu geschrieben:

Code: Alles auswählen

def summen(zahl, bereichvon, bereichbis):	
	list_=[]
	for i1 in range(bereichvon, bereichbis):
			for i2 in range(bereichvon, bereichbis):
				if  i2 != i1 and i1+i2 < zahl:
					for i3 in range(bereichvon, bereichbis):
						i4=zahl-i3-i2-i1
						if i4 > 0 and len(set([i1,i2,i3,i4])) == 4:
							x=[i1,i2,i3, i4]
							x.sort()
							list_.append(tuple(x))
	all=set(list_)
	print len(all),  " Summen gefunden!"
	return all
Die funktioniert auch wunderbar (obwohl, kann man die set-Menge noch sortieren?), nur finde ich sie nicht sonderlich schön.
Und je nachdem wie variabel man es machen will, also die Summandenzahl auch noch ändern will, ist dieser Weg bestimmt auch nicht der schnellste. Also, wie kann man das noch machen?

Auch etwas sonderbare Lösungen, wie die im "e-Zähl-Thread" wären cool.

Gruß, jj
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Freitag 18. Mai 2007, 16:56

Wenn du hier im Forum nach "backtracking" suchst findest du meinen Solver für magische Quadrate. Ich hab ihn ein wenig umgebaut. Sollte dir das Backtracking zu langsam sein müsstest du "unmögliche" Lösungswege bereits früher "vernichten".

Code: Alles auswählen

#!/usr/bin/python
# -*- coding: utf-8 -*-

class Permutation(object):
    def __init__(self, width, nums, abort):
        self.width = width
        self.nums = nums
        self.abort = abort
        self.sol = [0] * width

    def solve(self, where = 0):
        for count in range(1, self.nums+1):
            if count not in self.sol:
                self.sol[where] = count
                if where==self.width-1:
                    if sum(self.sol) == self.abort:
                        print "%s = %s" % (self.sol, sum(self.sol))
                else:
                    self.solve(where+1)

                self.sol[where] = 0

mysolver = Permutation(4, 12, 26)
mysolver.solve()
Eigentlich sollte man auf diese Weise den kompletten Stern lösen können. Viel Spaß beim lösen :)

lg herby

edit: sry, war ein mix aus spaces und tabs
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Freitag 18. Mai 2007, 17:06

Ehm...vlt. steh ich etwas aufm Schlauch, aber soweit war ich auch schon...
Ich muss ja jetzt aus den möglichen Summen noch 6 passende raussuchen und zusammensetzen. Und ob das durch einfaches Probieren in einer Schleife über alle Summen jemas fertig wird, hängt von der Definition jemals ab...
BlackJack

Freitag 18. Mai 2007, 17:07

Wenn man die sich den Stern aufmalt und die Knoten von oben nach unten und links nach rechts durchnummeriert, kann man das Problem mathematisch beschreiben:

Code: Alles auswählen

a1 + a4 +  a7 + a11 = 26
a1 + a3 +  a6 +  a8 = 26
a2 + a3 +  a4 +  a5 = 26
a2 + a6 +  a9 + a12 = 26
a5 + a7 + a10 + a12 = 26
a8 + a9 + a10 + a11 = 26
Mit der zusätzlichen Einschränkung, dass `a1` bis `a12` paarweise verschieden sein müssen. Dann brauchst Du nur noch "brute force" alle Möglichkeiten die 12 Variablen zu belegen auf die Gleichungen testen. Sind ja nur 479001600 Stück. Wenn man pro Prüfung eine Millisekunde braucht, steht spätestens in etwas mehr als 5½ Tagen eine Lösung fest. :-)

Mit der mathematischen Beschreibung kann man natürlich auch eine Bibliothek füttern, die einen "Finite Domain Constraint Solver" implementiert. Dort gibt man einfach die Variablen (`a1` bis `a12`), den endlichen Wertebereich ("finite domain") für jede Variable (1 bis 12 für `a1` bis `a12`) und die Einschränkungen ("constraints") an; das wären die sechs Formeln und das alle Variablen mit verschiedenen Werten belegt werden müssen. Dann sagt man der Bibliothek: Bitte lösen. :-)

Für Python gibt's zum Beispiel ein Package von Logilab, mit dem eine Lösung so aussehen könnte:

Code: Alles auswählen

from logilab.constraint import fd, Repository, Solver

def main():
    def make_variable_names(nodes):
        return ['a%d' % i for i in nodes]
    
    def make_sum_constraint(nodes):
        return fd.make_expression(nodes, '+'.join(nodes) + ' == 26')

    variables = make_variable_names(xrange(1, 13))
    domains = dict((v, fd.FiniteDomain(range(1, 13))) for v in variables)
    
    line_variables = map(make_variable_names, ((1, 4, 7, 11),
                                               (1, 3, 6, 8),
                                               (2, 3, 4, 5),
                                               (2, 6, 9, 12),
                                               (5, 7, 10, 12),
                                               (8, 9, 10, 11)))
    constraints = map(make_sum_constraint, line_variables)
    constraints.append(fd.AllDistinct(variables))
    
    repository = Repository(variables, domains, constraints)
    solutions = Solver().solve_one(repository)
    print solutions
Das Programm findet bei mir in ca. 3 Sekunden eine Lösung. Alle 960 Lösungen werden in ungefähr 6 Minuten und 15 Sekunden gefunden. Wobei einige von denen natürlich isomorph sind.

Deine Teillösung für mögliche Kombinationen auf einer Geraden etwas verallgemeinert könnte man so aufschreiben:

Code: Alles auswählen

from itertools import ifilter


def iter_combinations(elements, length):
    def comb(accu):
        if len(accu) == length:
            yield tuple(sorted(accu))
        else:
            for element in elements:
                for result in comb(accu + (element,)):
                    yield result
    
    return comb(tuple())


def all_distinct(elements):
    return len(set(elements)) == len(elements)


def exact_sum(target, elements):
    return sum(elements) == target


def find_sums(target, elements, length):
    def predicate(summands):
        return all_distinct(summands) and exact_sum(target, summands)
    
    return sorted(set(ifilter(predicate, iter_combinations(elements, length))))


def main():
    sums = find_sums(26, xrange(1, 13), 4)
    print sums
    print len(sums)
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Freitag 18. Mai 2007, 17:28

Hi BlackJack!
Erstmal: "Boh, ey!"
Man muss nur die richtigen Module kennen und sie verstehen...
Echt tolle Lösung! (was muss ich dafür alles installen? "nur" logilab-common und logilab-constraint?)

Das Problem: Eigentlich ging es nicht darum eine Lösung durch probieren (oder probieren lassen) zu finden, sondern eine mathematisch-logische Lösung oder einen solchen Weg zu finden. Alle möglichen Summen wollte ich nur finden, weil ich dachte, das könnte mir was sagen, und beim programmieren der Funktion wollte ich dann einfach schauen, wies am besten geht. Da ich aber nicht wirklich viele Module kenne, bzw. eigentlich nur die, die schon standartmäßig dabei sind, hatte ich wohl keine change, obwohl mein Weg ja auch nicht sooo schlecht ist...

Beim logischen Beschreiben des Problems war ich auch schon so weit, aber danach kam/komm ich nicht weiter.
Bei einem anderen Rätsel dieser Art, mit Dreiecken und Summen der Eckpunktzahlen, bin ich letztendlich zu einem Beweis gekommen und hatte einen richtigen Lösungsweg, aber das war auch etwas anders als hier...

Auch wenns Offtopic wird, gibt es hier auch einen logischen Lösungsweg?

mfg, jj
BlackJack

Freitag 18. Mai 2007, 18:27

Das Paket braucht wohl nur noch `logilab.common` als andere externe Abhängigkeit.

Was heisst "logischer" Lösungsweg? Das Unterproblem für eine Linie ist schon nicht effizient lösbar, da NP-vollständig. Das ist ein Problem, das eng verwandt mit dem "subset sum"-Problem ist.

Ein "Finite Domain Constraint Solver" geht normalerweise recht "logisch" an die Probleme heran, indem er Werte für die Variablen einsetzt und schaut in, wie weit die Wertebereiche für die anderen Variablen dadurch auf Grund der Beschränkungen eingeschränkt werden. Da hier jede Variable von der Belegung der anderen abhängt, läuft das letztendlich darauf hinaus, dass dieses Vorgehen ähnlich einer Backtracking-Lösung mit "branch and bound"-Optimierung ist.
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Freitag 18. Mai 2007, 19:15

ehm...ja...
Ich wollte damit eigentlich sagen, dass ich es ohne Computer lösen wollte, und zwar auf einem logischen Weg, da Ausprobieren blöd ist.
Um diesen logischen Weg zu finden hab ich ein bisschen rumprobiert und mir die möglichen Summen angesehen, aber ich wollte eigentlich kein Programm zum Lösen der Aufgabe schreiben, sondern halt nur mit Hilfe des PCs auf eine Idee kommen, wie man es "mit Stift und Papier" lösen kann.
EyDu
User
Beiträge: 4871
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Freitag 18. Mai 2007, 20:34

Händisch wirst du das sicher nicht lösen können, da dies schon der logische Weg ist. Da ist bei NP-vollständigen Problemen nichts mehr zu holen.

Deine Frage fällt übrigens ins Gebiet der "Wissensbasierten Systeme", falls dich dieser Bereich interessieren sollte.
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Samstag 19. Mai 2007, 12:23

Irgentwie hab ich leichte Probleme beim Installieren von den Logilab Sachen, bzw. eher schon beim Download...
Auf der Logilab Seite gehts iwie net...
Gibts das sonst noch wo?
Gruß, jj
BlackJack

Samstag 19. Mai 2007, 13:24

Also bei mir geht's mit:

Code: Alles auswählen

sudo apt-get install python-constraint
:-D
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Sonntag 20. Mai 2007, 10:39

...Bei mir aber nicht... :?
rafael
User
Beiträge: 189
Registriert: Mittwoch 26. Juli 2006, 16:13

Sonntag 20. Mai 2007, 11:47

schlangenbeschwörer hat geschrieben:...Bei mir aber nicht... :?
Liegt vielleicht daran, dass es (zumindest in Ubuntu) in universe liegt.
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Sonntag 20. Mai 2007, 13:22

...ich hab aber noch windows...
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Sonntag 20. Mai 2007, 13:28

Eventuell zum entwickeln mit Python eine Virtuelle Maschine installieren?
vmware player und server sind kostenfrei erhältlich(als download) genauso wie fertige images für div. Betriebssysteme.

lgherby
Antworten