Anzeige
Archiv - Navigation
1152to1156
Aktuelles Verzeichnis
Verzeichnis Index
Übersicht Verzeichnisse
Vorheriger Thread
Rückwärts Blättern
Nächster Thread
Vorwärts blättern
Anzeige
HERBERS
Excel-Forum (Archiv)
20+ Jahre Excel-Kompetenz: Von Anwendern, für Anwender
Inhaltsverzeichnis

Geht das mit Array?

Geht das mit Array?
alifa
Hallo Forum,
Dieses Problem ist keine Haus- oder andere Aufgabe. Ich habe ein brute-force Makro dafür geschrieben. Doch ist das zu langsam.
Gesucht ein zweidimensionales Array mit folgenden Eigenschaften:
1. Größe 7x7
2. In jeder Reihe und jeder Spalte sind genau alle Zahlen von 1 bis 7 enthalten.
3. a1=5;b1<5;d1>c1;d1>e1;e1>f1;g1=1;a2=2;b2=5;d2>c2;b 3>a3;d3>d2;e3<5;
f3=5;g3=3;b4>b3;c4>d4;f4>g4;a5=6;c5>d5;d5>e5;g5>f5 ;d6=1;a7>a6;e7>d7.
Das Ergebnis in Tabelle 1, also 7 Zeilen und 7 Spalten. a1=A1
Ich nimm an, es gibt nur eine Lösung. Mit der Hoffnung, dass jemand mir helfen kann,
Gruß, Erhard
Tabelle der Möglichkeiten
17.04.2010 16:50:31
Erich
Hi Erhard,
aus den Bedingungen habe ich mal eine Tabelle mit den reduzierten Möglichkeiten gemacht.
("1 - 5" bedeutet 1 bis 5, "3+4" bedeutet, dass nur die Ziffern 3 und 4 möglich sind).
 ABCDEFG
152 - 42 - 672 - 62 - 41
2251 - 43+41 - 71 - 72 - 7
31+42 - 674+61 - 453
41 - 73 - 72 - 62 - 61 - 72 - 72 - 6
561 - 73 - 52 - 41 - 31 - 42 - 7
63+42 - 72 - 612 - 72 - 72 - 7
74+71 - 71 - 62 - 62 - 71 - 72 - 7

Die blauen Zellen waren schon in der Aufgabe gesetzt, die beiden grünen ergeben sich m. E. logisch.
Zuerst ergibt sich die 7 in Zeile 1 - die kann sonst nirgends stehen.
Mal schauen, ob ich mehr rausbekomme...
Rückmeldung wäre nett! - Grüße von Erich aus Kamp-Lintfort - und: Schönes WoEnde!
Anzeige
AW: Tabelle der Möglichkeiten
17.04.2010 21:33:20
alifa
Hi Erich,
Ich habe es jetzt mit 7 siebenstelligen Zahlen versucht. Die Bedingungen der verschiedenen Ziffern zunächst nur auf die Reihen angewendet. Ich habe im Netz die Funktion "isUniq" gefunden. Wenn a die Zahl(siebenstellig)ist, dann lautet die Syntax z.B. If isUniq(a) Then...
Function isUniq(ByVal lngZahl As Long) As Boolean
Dim i As Integer
Dim strZahl As String
strZahl = Mid(CStr(lngZahl), 1)
For i = 1 To 7
If InStr(strZahl, Mid("1234567", i, 1)) 

Gruß, Erhard
in ca. 20 Sekunden...
18.04.2010 19:10:25
Erich
Hi Erhard,
folgender Code spuckt in weniger als einer halben Minute 114 Lösungen
auf dem aktuellem Tabellenblatt aus:

Option Explicit
Dim pp(1 To 5040, 1 To 7) As Byte
Sub PermStart()
Const tt$ = "1234567"
Dim ii As Long, jj As Long, nn As Long
Dim k1 As Long, k2 As Long, k3 As Long, k4 As Long, k5 As Long, k6 As Long, k7 As Long
Dim z1 As Long, z2 As Long, z3 As Long, z4 As Long, z5 As Long, z6 As Long, z7 As Long
z1 = 0
Perm tt, "", z1
For z1 = 1 To 5040
If pp(z1, 1) = 5 And pp(z1, 2)  pp(z1, 3) And _
pp(z1, 4) > pp(z1, 5) And pp(z1, 5) > pp(z1, 6) And pp(z1, 7) = 1 Then
k1 = k1 + 1
For z2 = 1 To 5040
If pp(z2, 1) = 2 And pp(z2, 2) = 5 And pp(z2, 4) > pp(z2, 3) Then
For ii = 1 To 7
If pp(z1, ii) = pp(z2, ii) Then Exit For
Next ii
If ii = 8 Then
k2 = k2 + 1
For z3 = 1 To 5040
If pp(z3, 2) > pp(z3, 1) And pp(z3, 4) > pp(z2, 4) And _
pp(z3, 5)  pp(z3, 2) And pp(z4, 3) > pp(z4, 4) And _
pp(z4, 6) > pp(z4, 7) Then
For ii = 1 To 7
If pp(z1, ii) = pp(z4, ii) Then Exit For
If pp(z2, ii) = pp(z4, ii) Then Exit For
If pp(z3, ii) = pp(z4, ii) Then Exit For
Next ii
If ii = 8 Then
k4 = k4 + 1
For z5 = 1 To 5040
If pp(z5, 1) = 6 And pp(z5, 3) > pp(z5, 4) And _
pp(z5, 4) > pp(z5, 5) And _
pp(z5, 7) > pp(z5, 6) Then
For ii = 1 To 7
If pp(z1, ii) = pp(z5, ii) Then Exit For
If pp(z2, ii) = pp(z5, ii) Then Exit For
If pp(z3, ii) = pp(z5, ii) Then Exit For
If pp(z4, ii) = pp(z5, ii) Then Exit For
Next ii
If ii = 8 Then
k5 = k5 + 1
For z6 = 1 To 5040
If pp(z6, 4) = 1 Then
For ii = 1 To 7
If pp(z1, ii) = pp(z6, ii) Then Exit For
If pp(z2, ii) = pp(z6, ii) Then Exit For
If pp(z3, ii) = pp(z6, ii) Then Exit For
If pp(z4, ii) = pp(z6, ii) Then Exit For
If pp(z5, ii) = pp(z6, ii) Then Exit For
Next ii
If ii = 8 Then
k6 = k6 + 1
For z7 = 1 To 5040
If pp(z7, 1) > pp(z6, 1) And pp(z7, 5) > pp(z7, 4) Then
For ii = 1 To 7
If pp(z1, ii) = pp(z7, ii) Then Exit For
If pp(z2, ii) = pp(z7, ii) Then Exit For
If pp(z3, ii) = pp(z7, ii) Then Exit For
If pp(z4, ii) = pp(z7, ii) Then Exit For
If pp(z5, ii) = pp(z7, ii) Then Exit For
If pp(z6, ii) = pp(z7, ii) Then Exit For
Next ii
If ii = 8 Then
k7 = k7 + 1
nn = nn + 1
For ii = 1 To 1
Cells(nn, 8) = k7
nn = nn + 1
For jj = 1 To 7
Cells(nn, jj) = pp(z1, jj)
Cells(nn + 1, jj) = pp(z2, jj)
Cells(nn + 2, jj) = pp(z3, jj)
Cells(nn + 3, jj) = pp(z4, jj)
Cells(nn + 4, jj) = pp(z5, jj)
Cells(nn + 5, jj) = pp(z6, jj)
Cells(nn + 6, jj) = pp(z7, jj)
Next jj
nn = nn + 6
If nn > 20 Then ActiveWindow.SmallScroll down:=8
Next ii
End If
End If
Next z7
End If
End If
Next z6
End If
End If
Next z5
End If
End If
Next z4
End If
End If
Next z3
End If
End If
Next z2
End If
Next z1
End Sub
Sub Perm(aa$, bb$, Ze&)
Dim ii%, jj%:     jj = Len(aa)
If jj > 1 Then
For ii = 1 To jj
Perm Left(aa, ii - 1) + Right(aa, jj - ii), bb + Mid(aa, ii, 1), Ze
Next ii
Else
Ze = Ze + 1
If Ze > UBound(pp) Then Stop
For ii = 1 To 6
pp(Ze, ii) = Mid(bb, ii, 1)
Next ii
pp(Ze, 7) = aa
End If
End Sub
Viel Spaß!
Rückmeldung wäre nett! - Grüße von Erich aus Kamp-Lintfort
Anzeige
AW: in ca. 20 Sekunden...
19.04.2010 07:07:58
alifa
Hallo Erich,
in Deinem Makro ist Musik drin! Sogar der Name des Arrays stammt aus der Richtung. Das Makro läuft bei mir 8 Sekunden.
Danke!!
Erhard
AW: Geht das mit Array?
17.04.2010 20:32:48
ChristianM
Hallo Erhard,
Die Antwort auf deine Frage: "geht das mit Array" lautet eindeutig: Ja!
Denn ein Array ist ein ein- oder mehr-dimensionales Datenfeld. Hier kannst du reinschreiben, was immer dir in den Sinn kommt.
Doch zurück zu deiner Aufgabe:
Du sagst, deine Brute Force Methode ist zu langsam - Nun... bei dem "Ausprobieren aller möglichen Fälle" würdest du schlimmstenfalls 50407 = 8 * 1025 Möglichkeiten untersuchen.
Nehmen wir an, deine Rechner könnte in einer Sekunde 1 Milliarde Operationen ausführen, dann würde er für diese Aufgabe schlappe 2,6 Millarden Jahren benötigen...
Brute Force heißt ja aber nicht, dass man ohne Hirn an die Sache rangeht.
Daher mein Vorschlag:
- berechne die 5040 möglichen Permutationen.
- überprüfe für jede der 7 Zeilen diese Permutationen auf die genannten Bedingungen.
Und genau da ist ein bisschen Logik gefragt...
... z.B. für Zeile 3:
Vorgabe:
- b3 > a3
- d3 > d2 - zeilenübergreifend!
- e3 < 5
- f3 = 5
- g3 = 3
Bedingungen aus den weiteren Zeilen sind:
- g3 <> 1, da g1 = 1 nicht relevant, da g3 = 3
- a3 <> 5, da a1 = 5 nicht relevant, da f3 = 5
- a3 <> 2, da a2 = 2
- b3 <> 5, da b2 = 5 nicht relevant, da f3 = 5
- a3 <> 6, da a5 = 6
Um alle den vorgegebenen Bedingungen entsprechende Permutationen pro Zeile zu erhalten, dürfen zeilenübergreifende Bedingungen wie "d3 > d2" hierhei erst ganz zum Schluss beachtet werden. Bedingungen dieser Art sind daher gleichbedeutend mit der Forderung, dass die Ziffern auch innerhalb einer "Spalte" unterschiedlich sein müssen.
Wenn du dieses Prinzip für alle 7 Zeilen anwendest, kommst du nach einer ersten überschlägigen Rechnung nach geschätzten 2 bis 3 Minuten Rechenzeit auf 69 verschiedene Lösungen.
In anbetracht dessen, dass die Aufgabenstellung reine Zahlenspielerei darstellt, könnte ich mit eine Rechenzeit von 2-3 Minuten leben.
Grüße
Christian
Anzeige
AW: Geht das mit Array?
17.04.2010 21:22:20
alifa
Hallo Christian,
Es gibt wahrscheinlich nur eine Lösung! In jeder Spalte müssen auch alle Ziffern unterschiedlich sein. Das aus der Bedingung 2.(In jeder...Spalte sind genau alle Zahlen[Ziffern] von 1 bis 7 enthalten)Das bedeutet, dass alle Ziffern unterschiedlich sind. Tatsächlich kann man einige Bedingungen weglassen. Ich habe es mit der Funktion "isUniq" versucht. Da gibt es weniger Varianten. Nach 4 Stunden tat sich nichts...
Gruß, Erhard
AW: Geht das mit Array?
17.04.2010 22:37:55
ChristianM
Hallo Erhard,
hättest du meine Antwort gelesen, wäre dir meine Formulierung: "dass die Ziffern auch innerhalb einer "Spalte" unterschiedlich sein müssen." aufgefallen. Ergo berücksichtigt mein Ansatz diese Bedingung.
Insofern bleibe ich bei meiner ersten Schätzung: Es gibt 69 Lösungen.
als Bsp zwei der mögl. Lösungen - korrigiere mich bitte, sollte ich falsch liegen...
5 2 6 7 4 3 1
2 5 1 3 7 4 6
1 4 7 6 2 5 3
3 6 4 2 1 7 5
6 7 5 4 3 1 2
4 3 2 1 5 6 7
7 1 3 5 6 2 4
und:
5 3 2 7 6 4 1
2 5 1 3 4 7 6
1 4 7 6 2 5 3
4 7 6 5 1 3 2
6 2 5 4 3 1 7
3 6 4 1 7 2 5
7 1 3 2 5 6 4
Gruß
Christian
Anzeige
AW: Geht das mit Array?
18.04.2010 06:13:03
alifa
Hallo Christian,
ich hatte eine ähnliche Aufgabe, allerdings mit 5x5. Das konnte ich mit brute force in 40 Minuten lösen. Da gab es tatsächlich nur eine Lösung. Irgendwo hab ich gelesen, dass ein Rätsel mit mehreren Lösungen als "fake" gesehen wird (in England) Von daher meine, wie Du bewiesen hast, falsche Annahme. Auf Dein Makro bin ich gespannt. Die erwähnte Aufgabe stammte aus derselben Quelle.
Gruß, Erhard
Weiß nicht, wie du immer zu deinen gigantischen...
18.04.2010 21:59:46
Luc:-?
…Laufzeiten kommst, Erhard,
die sehen nach fake aus, oder hast du noch einen „Dampf-PC“ von 1960… ;-)
Gruß Luc :-?
AW: Weiß nicht, wie du immer zu deinen gigantischen...
18.04.2010 22:49:16
alifa
Wann sehe ich von dir endlich etwas Anständiges, außer solchen fruchtlosen, groben Bemerkungen?!
Falls du wirklich etwas kannst, so zeige es doch, jetzt hättest du die Gelegenheit. Lass sie doch nicht ungenutzt verstreichen!
Gruß, Alifa
Anzeige
Dein antiker Mathekram interessiert mich...
19.04.2010 05:14:46
Luc:-?
…nicht die Bohne, Alifa,
ich habe Besseres zu tun…
Meine gelegentl, überwiegend von deinen eigenen Angaben provozierten Bemerkungen scheinen dich ja so zu nerven, dass dir der Unterschied zwischen grob und witzig trotz Smily abhanden gekommen zu sein scheint… :->
Außerdem muss ich nicht auf deine Gelegenheiten warten, ich habe genug eigene Ideen, bspw echte Bedingtformatierung mit >3 Bedingungen vor xl12… So etwas und neu(artig)e Fktion(alität)en interessieren mich. Kannst du leicht herausfinden, wenn du aufhörst, im Eigensaft zu schmoren…
Morrn, Luc :-?
Anzeige
...nicht mehr wg oft genug fehld Rückmeld! owT
19.04.2010 14:48:40
Luc:-?
:-?

Beliebteste Forumthreads (12 Monate)

Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige
Anzeige
Anzeige