Alle möglichen kombinationen von 5 Arrays

[Manni]

Guten Abend

ich habe hier 5 Arrays.

String[] musik =
{"Madonna","Beatles","Heino","Eminem","Abba"};
String[] autos =
{"Ferrari","VW","BMW","Smart","Ford"};
String[] farben =
{"rot","silbern","blau","braun","gruen"};
String[] staedte =
{"Hamburg","Muenchen","Koeln","Berlin","Stuttgart"};
String[] berufe =
{"Lehrer","Notar","Metzger","Schreiner","Baecker"};

Jetzt habe ich hier ein Rätselt so nach dem Motto das auto des Metzgers steht neben dem Auto aus München und das blaue auto neben dem braunen etc.

Wie kann ich jetzt die Arrays in allen möglichen Kombinationen überprüfen ob sie das Rätsel erfüllen? die Bedingungen habe ich schon programmiert ich brauche nur noch eine Funktion die nachheinander immer eine mögliche Kombination weitergeht....

ich steh da irgendwie gerade aufm Schlauch, ich hoffe ihr könnt helfen

danke sehr

[Christoph Schnauß]

hallo,

Wie kann ich jetzt die Arrays in allen möglichen Kombinationen überprüfen

Wenn du wirlich "alle möglichen" meinst, ist das eine relativ einfache Mathematikaufgabe. Dafür wurde die Faktorrechnung erfunden. Bei 5 Arrays hast du genau 5x4x3x2x1 - also 120 Möglichkeiten, die du einzeln überprüfen möchtest.

Grüße aus Berlin

Christoph S.

[Manni]

ja, das wäre bei einem Array der größe 5 aber ich hab ja davon 5 also ergibt sich dann ja denke ich

(120)^5 Möglichkeiten

und dafür brauch ich halt ne Funktion, die in einer while Schleife so lange eine Möglichkeit nach der anderen testet, bis eine passende kombination aus allen 5 Arrays gefunden wurde.....

[Sven Rautenberg]

Moin!

ja, das wäre bei einem Array der größe 5 aber ich hab ja davon 5 also ergibt sich dann ja denke ich

(120)^5 Möglichkeiten

und dafür brauch ich halt ne Funktion, die in einer while Schleife so lange eine Möglichkeit nach der anderen testet, bis eine passende kombination aus allen 5 Arrays gefunden wurde.....

Im Kopf die Lösung ermitteln geht vermutlich schneller.

Wie du ja schon richtig vermutet hast, hast du 120^5 Möglichkeiten. Also mehr als 24 Milliarden.

Angenommen, dein Programm prüft pro Sekunde 1000 Möglichkeiten durch, würde es 288 Tage lang laufen, um alle Möglichkeiten abzuprüfen. Klingt nicht so besonders verlockend. :)

Der Ansatz mit Backtracking erscheint mir da doch deutlich besser, das reduziert die Suche nach weiteren Lösungen dann, wenn schon klar ist, dass eine Sackgasse gefunden wurde.

- Sven Rautenberg

[Martin L.]

so, ich gehe jetzt erst mal zur schule werde mir aber eure Vorschläge mal anschauen.... und sonst hat mein PC halt mal ein paar Tage was zu tun :-D

trotzdem habe ich noch das Problem, wie ich eine Funktion schreibe die einfach nacheinander alle Möglichkeiten auswählt.... aber da ich jetzt ja wiß wie viele Möglichkeiten es gibt, kann ich ja noch mal nachdenken...

[seth]

gudn tach!

Angenommen, dein Programm prüft pro Sekunde 1000 Möglichkeiten durch

das waere afais aber ein sehr lahmer computer.
die bedingungen sollten sich als einfache aneinanderkettung (mittels lazy AND) von vergleichen aufstellen lassen. angenommen es waeren 15 vergleiche, dann kommt selbst meine 466MHz-kruecke mit perl im worst case auf knapp 10^6 durchlaeufe pro sekunde (im best case kommt noch ca. faktor 6 drauf). die dauer beliefe sich dann noch auf ca. 7 h.
ich wuerde also nicht aussschliessen, dass ein moderner computer selbst bei der brute-force-methode gegen einen menschen gewinnen koennte (wenn man von der programmier-dauer mal absieht).

Der Ansatz mit Backtracking erscheint mir da doch deutlich besser

das will ich nicht bestreiten.

prost
seth

[Norbert]

Hallo,

und dafür brauch ich halt ne Funktion, die in einer while Schleife so lange eine Möglichkeit nach der anderen testet, bis eine passende kombination aus allen 5 Arrays gefunden wurde.....

hmm,
schreibe es in PHP, geht mir leichter von der Hand:

<pre><hr><?  
$SET = array(  
    array('A'=>'Ford',   'B'=>'Notar',   'F'=>'gruen', 'M'=>'Beatles', 'O'=>'Berlin'),  
    array('A'=>'Ferrari','B'=>'Lehrer',  'F'=>'rot',   'M'=>'Madonna', 'O'=>'München'),  
    array('A'=>'BMW',    'B'=>'Metzger', 'F'=>'blau',  'M'=>'Heino',   'O'=>'Köln'));  
  
$ATS = array('Ferrari','VW','BMW','Smart','Ford');  
$BRF = array('Lehrer','Notar','Metzger','Schreiner','Baecker');  
$FRB = array('rot','silbern','blau','braun','gruen');  
$MSK = array('Madonna','Beatles','Heino','Eminem','Abba');  
$ORT = array('Hamburg','München','Köln','Berlin','Stuttgart');  
foreach($SET as $RUN) {  
    echo 'gesucht:  '.$RUN['A'].' | '.$RUN['B'].' | '.$RUN['F'].' | '.$RUN['M'].' | '.$RUN['O']."\n";  
    foreach($ATS as $auto) {  
        if ($RUN['A'] == $auto) { break; }  
    }  
    foreach($BRF as $beruf) {  
        if ($RUN['B'] == $beruf) { break; }  
    }  
    foreach($FRB as $farbe) {  
        if ($RUN['F'] == $farbe) { break; }  
    }  
    foreach($MSK as $musik) {  
        if ($RUN['M'] == $musik) { break; }  
    }  
    foreach($ORT as $stadt) {  
        if ($RUN['O'] == $stadt) { break; }  
    }  
    echo 'gefunden: '.$auto.' | '.$beruf.' | '.$farbe.' | '.$musik.' | '.$stadt."\n<hr>";  
}  
?></pre>

Code in eine Textdatei kopieren, test.php nennen und von einem Webserver aufrufen.

Im ersten Array stehen drei Variationen, die es zu erraten gilt.
Foreach durchwandert ein Array und beginnt immer mit dem ersten Element.

Es ist einfach, weil bekannt ist wo ein Auto stehen kann und wo ein Ort.
Das nach Java zu portieren kann jetzt kein Problem sein - oder ... ;-)

Gruss und Dank
Norbert

[Sven Rautenberg]

Moin!

Im ersten Array stehen drei Variationen, die es zu erraten gilt.
Foreach durchwandert ein Array und beginnt immer mit dem ersten Element.

Es ist einfach, weil bekannt ist wo ein Auto stehen kann und wo ein Ort.
Das nach Java zu portieren kann jetzt kein Problem sein - oder ... ;-)

Dein Code ist zwar sehr schön, löst aber leider nicht die Aufgabe. Tatsächlich verbrät er nur unnötig Rechenzeit, um in mehreren seriellen Schleifen in anderen Arrays genau das wiederzufinden, was im Sucharray schon fest vorgegeben ist.

Die Aufgabe ist, aus Logiksätzen wie diesen die Platzierung und Zuordnung der Fahrzeuge auf dem Parkplatz zu ermitteln.

1. Der Mercedes steht neben dem Ford.
2. Das Lehrerauto steht neben dem Auto, in dem Heino singt.
3. Der Fahrer aus München mag Eminem.

- Sven Rautenberg

[Norbert]

Hallo Sven,

Dein Code ist zwar sehr schön, löst aber leider nicht die Aufgabe.

schade

Die Aufgabe ist, aus Logiksätzen wie diesen die Platzierung und Zuordnung der Fahrzeuge auf dem Parkplatz zu ermitteln.

1. Der Mercedes steht neben dem Ford.
2. Das Lehrerauto steht neben dem Auto, in dem Heino singt.
3. Der Fahrer aus München mag Eminem.

hmm,
und wo bekommt man eine komplette Aufgabenstellung her?
IMHO wurde sie hier nicht gepostet ...

Gruss und Dank
Norbert

[seth]

gudn tach!

und wo bekommt man eine komplette Aufgabenstellung her?
IMHO wurde sie hier nicht gepostet ...

die komplette aufgabenstellung ist fuer das prinzipielle loesen des problems nicht erforderlich.

prost
seth

[Norbert]

Hallo,

die komplette aufgabenstellung ist fuer das prinzipielle
loesen des problems nicht erforderlich.

hmm,
was meint der Prof nach der Klausur dann:
    Das Ergebnis ist zwar total falsch aber wegen
    der sehr guten prinzipiellen Loesung sind sie
    zur Nachklausur zugelassen, Glueckwunsch seth!

Nee, mal im Ernst. Es gibt doch nur 3.125 Moeglichkeiten, wie
die Wagen auf den 5 Plaetzen angeordnet sein koennen. Wobei sie
alle gestellten Bedingungen (Aufgabenstellung) erfuellen muessen.

Wenn man es nun schafft, die Aufgabenstellung in abfragbare
logische Ausdruecke umzusetzen, ist der Rechner in wenigen
Millisekunden damit fertig.
Ohne Aufgabenstellung haben wir jedoch ein Problem ... ;-)

Gruss und Dank
Norbert

[seth]

gudn tach!

Nee, mal im Ernst. Es gibt doch nur 3.125 Moeglichkeiten, wie
die Wagen auf den 5 Plaetzen angeordnet sein koennen.

nein, nicht 5^5, sondern 5! = 120.

Wobei sie alle gestellten Bedingungen (Aufgabenstellung) erfuellen muessen.

eben, und da noch zusaetzlich zu den parkplaetzen die anderen fuenf eigenschaften (auto, autofarbe, musik etc.) den leuten zugewiesen werden sollen, ergeben sich insg. (5!)^5 moeglichkeiten.
falls das raetsel noch nicht klar ist, vgl. http://en.wikipedia.org/wiki/Zebra_Puzzle.

Wenn man es nun schafft, die Aufgabenstellung in abfragbare
logische Ausdruecke umzusetzen, ist der Rechner in wenigen
Millisekunden damit fertig.

siehe postings von Sven und antworten von mir.

Ohne Aufgabenstellung haben wir jedoch ein Problem ... ;-)

nein. die aufgabenstellung lautet:

"Wie kann ich jetzt die Arrays in allen möglichen Kombinationen überprüfen ob sie das Rätsel erfüllen? die Bedingungen habe ich schon programmiert ich brauche nur noch eine Funktion die nachheinander immer eine mögliche Kombination weitergeht...." (siehe OP)

d.h., die testfunktion soll als gegeben vorausgesetzt werden. quasi als blackbox, wobei man sie fuers backtracking modifizieren muesste.
das ist eine loesbare aufgabe und Daniel Thoma hat einen loesungsweg skizziert.

prost
seth

[Norbert]

Hallo,

da noch zusaetzlich ... anderen fuenf eigenschaften ...
zugewiesen werden sollen, ergeben sich insg. (5!)^5 moeglichkeiten.
..., vgl. Das Zebrarätsel (auch "Einstein-Rätsel").

danke,
genau das hat mir gefehlt ...

Gruss und Dank
Norbert

[Daniel Thoma]

Hallo Manni,

Wie genau möchtest Du Kombinationen auswählen?
Wird aus jedem Array immer ein Element gewählt?

Generell ist es keine gute Idee solche Probleme durch explizites Aufzählen aller Kombinationen zu lösen. Das ist nur machbar, wenn man sehr wenige, zu kombinierende Elemente hat, was bei Dir je nach Problemstellung noch der Fall sein könnte.

Grüße

Daniel

[martin L.]

ich habe glaub ich wirklich das Problem der zu vielen Möglichkeiten aber wie ich es anders umsetzten sollte wüsste ich auch nicht und ich will nicht in die Lösung schauen :-D

also es geht um einen Parkplatz wo halt die autos mit den jeweiligen farben zu der jeweiligen musik, stadt und beruf des besitzers zugeordnet sind

also zum beispiel

Ferrari rot München Madonna Lehrer
BMW blau Köln Heino Meztger

und ich hatte halt gedacht, alle möglichen Parkplatzsysteme auszuprobieren aber das scheint wohl unrealistisch.... trotzdem würde ich gerne wissen, mit welcher funktion man da alle möglichkeiten probieren könnte^^

[Martin L.]

nich wundern der Manni is kurz ähm mit nicht aufschiebbaren dingen beschäftigt ;-) deshalb hab ihc jetzt mal übernommen^^ wir sitzen echt schon Tage an dem Rätsel

[Daniel Thoma]

Hallo martin,

Ferrari rot München Madonna Lehrer
BMW blau Köln Heino Meztger

Ah ok, das sind die Daten und zusätzlich sind Bedingungen gegeben wie "BMW steht neben Ferrari", "rot neben grün" etc.?
Gesucht ist nun was? Die Reihenfolge in der die Autos geparkt sind?

Für solche Probleme eignet sich meist Backtracking oder fertige Software für Constraint Programming.
http://de.wikipedia.org/wiki/Backtracking@Backtracking ist in der Wikipedia recht ausführlich beschrieben. Die Idee ist es, nicht nacheinander Kombinationen auszuprobieren, sondern diese Schrittweise auszuwählen und an einer Stelle nicht weiter zu suchen, sobald man feststellt, dass das nicht geht.
Theoretisch ist es zwar möglich, dass man bei diesem Ansatz auch alle Kombinationen ausprobieren muss. Praktisch kann man das aber meist verhindern, indem man sich überlegt, wie man schon erkennen, dass eine Kombination nicht zulässig ist, bevor man alle Elemente festgelegt hat und das evtl. noch um Heuristiken erweiter, welche Art von Kombinationen zuerst untersucht werden sollten.

Ich würde als ersten Ansatz mal so etwas machen:
Belege der Reihe nach die Parkplätze, sobald eine Regel verletzt ist, breche ab und mache mit anderen Kombinationen weiter.
Wenn das nicht schon reicht, würde ich versuchen, immer zuerst Werte zu wählen, für die ich möglichst viele Regeln habe.
Funktioniert das auch nicht, würde ich mir überlegen, ob ich mir wirklich die Arbeit machen möchte oder doch erstmal eine fertige Software drauf ansetzen ;-)

Das Problem ist relativ einfach und lässt sich mit Aussagenlogik (siehe Wikipedia ;-) modellieren.
Wenn man das gemacht hat, könnte man z.B. Limboole darauf ansetzen und eine Lösung bestimmen lassen. Mit beliebig großen Problemen kommen solche Programme natürlich auch nicht klar. Aber es reicht schon für mehr als man mal so auf die Schnelle mit Backtracking gelöst bekommt.

Grüße

Daniel

[Daniel Thoma]

Der Link sollte natürlich so aussehen:
Backtracking

[Vinzenz Mai]

Hallo

Jetzt habe ich hier ein Rätselt so nach dem Motto das auto des Metzgers steht neben dem Auto aus München und das blaue auto neben dem braunen etc.

ich verwende dafür am liebsten brain 1.0.

Freundliche Grüße

Vinzenz