Autor |
Beitrag |
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 01.12.08 14:53
Hallo,
bei welchem n x n ?? n = 5??
Gruß Horst
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mo 01.12.08 15:21
ups, ja 
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 01.12.08 15:26
Hallo
das ist das 4+2/3 fache. merkwürdig.Wo habe ich den bei dem Bild den Fehler?
Quelltext 1: 2: 3: 4: 5: 6:
| Möglichkeiten der Auswahl.Beispiel für n = 5, 5 4 3 2 1 4 3 2 1 1 3 2 1 1 1 2 1 1 1 1 1 1 1 1 1 |
5!x4!x3!x2!x1! = 34560
Gruß Horst
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mo 01.12.08 15:46
Vorausgesetzt der Algorithmus haut hin...
Müsste nicht (Ai, j) = min{n-i-j, 1} sein?
Mit A € (Zn)^(nxn), wobei Zn die Restklasse modulo n sein soll...
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mo 01.12.08 15:49
Thorsten83 hat folgendes geschrieben : | Vorausgesetzt der Algorithmus haut hin...
Müsste nicht (Ai, j) = max{n-i-j, 1} sein?
Mit A € (Zn)^(nxn), wobei Zn die Restklasse modulo n sein soll... |
edit: sry, verklickt...
muss auf jeden Fall max und nicht min sein
edit2: Ich schreib auch nur noch Mist...
Die obige Formel gilt nur dann, wenn die Zahlen, die schon in der Spalte / Zeile stehen, alle unterschiedlich sind, was ja nicht zwangsläufig der Fall sein muss.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 01.12.08 15:56
Hallo,
meine Werte A[i,j] sind doch MAX(n-i-j,1)
Geht dein Backtracking falsch zurück oder zählt falsch?
Nimm doch mal n = 2 oder 3 das sind doch wirkich nur 2 oder 12 Lösungen
Gruß Horst
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mo 01.12.08 16:16
Ne, nimm folgende Anfangsbelegung:
Quelltext 1: 2: 3: 4:
| 0 1 2 3 1 x x x x x x x x x x x |
Dann ist A1,1€{0, 2, 3}, es gibt also 3 und nicht wie vermutet nur noch 2 Möglichkeiten.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 01.12.08 16:36
Hallo,
wahrlich wahr! Wenn also: in der selben Zeile in den vorangegangenen Spalten UND in der selben Spalte in den vorangegangenen Zeilen gleiche Zahlen vorkommen steigt die Anzahl der Möglichkeiten n-i-j um die Zahl der gleichen Zahlen Aber maximal auf n-max(i,j),also die längere Zeile oder Spalte an A(i,j) ist betimmend.
Erste Spalte und Zeile bleiben gleich aber dann:
Quelltext 1: 2: 3:
| 5 4 3 2 1 | 4--3+(4 gleiche /4*4(alle Kombinationen) 3,25 etc |
Das ist aber nicht mehr leicht zu berechnen
Ich bastel noch an der Logik für die Belegung herum:
wenn ich an einer Stelle eine Auswahlmenge die 4 beinhaltet habe und in den folgenden Spalten kommt jetzt überll schon 4 vor, habe ich pratisch keine Wahl sondern muss jetzt die 4 wählen.
Momentan arbeite ich mit TBits von freepascal. (XOR /AND OR ANDNOT etc)
Also bei den Spalten die Vereinigungsmenge bilden, und wenn diese Elemente aus der Auswahlmenge enthält nur diese nutzen, aber darf diese nicht nur ein-elementig ein.
Bei mehreren ist doch kein fortkommen möglich?
Gruß Horst
EDIT:
Trotz Zufallszahlen völlig symmetrisch, aber mit Fehler in Zeile 3 Spalte 3 falsch gewählt zu haben, sodass die 1 nicht mehr gesetzt werden kann.
Einloggen, um Attachments anzusehen!
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Mo 01.12.08 19:05
Hab meinen Rechner mal gequält während ich in der Uni war,
für eine 6x6-Matrix gibt's laut Backtracking 812851200 Möglichkeiten...
Rechenzeit waren wohl ca. 17 Minuten
Aber nur die Zahl hilft uns ja nicht weiter.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 01.12.08 21:14
Hallo,
Du hast deinen Rechner nicht umsonst geärgert:
www.research.att.com...as/sequences/A002860
en.wikipedia.org/wiki/Latin_square
Da kannst Du deinen Zahlen bestätigt finden.
Es wäre natürlich toll zu sagen:
ErzeugeLateinQuadratLfdNr(n,Random(MaxZahl(n));
ich habe mit zufälliger Auswahl auch ähnliche Ergebnisse wie freedy zu Beginn.
Natürlich ist es schneller ohne Stringgrid und ohne die Entfernung der Elemente in sortierter Form.
12 x12 in 1,8 statt 96.7 ms (100 Durchgänge), aber völlig nicht vorhersagbare Zeiten
n = 32 von 10ms bis 1107 ms
Aber mischen , selbst nxn-fach ,ist einfach viel schneller.
170 x 170 in 91 ms also die 200-fache Anzahl an Elementen gegenüber 12 x 12.
Ich glaube momentan nicht, das es viel Sinn macht, Feld für Feld zu belegen, denn die Testlogik dahinter braucht viel zuviel Zeit, sodass stumpfsinniges mischen schneller ist.
Gruß Horst
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 02.12.08 12:57
Ansonsten hab ich da einen interessanten Ansatz gefunden, allerdings erzeugt er nur n!(n-1)! Möglichkeiten.
Zur Feier des Tages wollte ich mal eine GUI fertigmachen, und da ich kein VS hier hab in java...
Jetzt frisst folgende Zeile mir die Haare vom Kopf, die Erstellung des Feldes geht verdammt schnell(63ms für 2048x2048-Matrix):
Quelltext 1: 2: 3: 4: 5: 6:
| for (i=0 ; i<n ; i++){ for (j=0 ; j<n ; j++){ result += String.format("%3d ", matrix[i][j]); } result+="\n"; } |
Achso, fast vergessen:
Der Algorithmus füllt die erste Spalte und erste Zeile per Fisher-Yates, und füllt dann die Matrix so, dass
Ai,j = (Ai,0 + A0,j) mod n
|
|
jaenicke
      
Beiträge: 19315
Erhaltene Danke: 1747
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Di 02.12.08 13:25
Thorsten83 hat folgendes geschrieben : | Zur Feier des Tages wollte ich mal eine GUI fertigmachen, und da ich kein VS hier hab in java... |
Eclipse + nen GUI-Designer, fertig  .
Wie du den Algorithmus meinst, ist mir noch nicht so ganz klar.
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 02.12.08 13:27
Hallo,
als ich so durch Internet nach latin sqaure etc suchte haben mehrere, auch Kryptografen, nur  n! x (n-1)! Varianten erzeugt. ( n = 16 sind ja nur 2^84 Möglichkeiten )
Wo ist dein Problem?
Geht es Dir um die Geschwindigkeit, bei Erstellung der Ausgabe.
C#-Quelltext 1: 2: 3: 4: 5: 6:
| for (i=0 ; i<n ; i++){ for (j=0 ; j<n ; j++){ result += String.format("%3d ", matrix[i][j]); } result+="\n"; } |
Strings sinmd immer ärgerlich lahm, der wird ja auch jedesmal komplett kopiert und bei 2048 auch ~4,1 Mio mal bei zunehmender Länge also immer neuer Speicherplatz.
In Delphi könnte man result auf die richtige Länge seztzen und den Formatteil mittels copy an die richtige Stelle schreiben
Gruß Horst
|
|
freedy 
      
Beiträge: 403
Erhaltene Danke: 1
Winows 7
Delphi XE
|
Verfasst: Di 02.12.08 14:15
Horst_H hat folgendes geschrieben : | Als ich so durch Internet nach latin sqaure etc suchte haben mehrere, auch Kryptografen, nur n! x (n-1)! Varianten erzeugt. ( n = 16 sind ja nur 2^84 Möglichkeiten ) |
Frage dazu: warum hat denn der Algorithmus für n x n-Matrizen dann solche Schwierigkeiten? Ich werde nun auch mal danach googlen.
Mischen ist natürlich schneller. Meine Befürchtung damals war halt nur, dass dann trotzdem noch aufeinander folgende Element zusammen stehen, z. B. 3, 4, 5 oder ähnlich. Das kann beim zufälligen Ausfüllen natürlich auch auftreten. Ist eine Frage der Häufig- und Wahrscheinlichkeit. Vielleicht müsste man Sicherstellen, dass jede Zeile bzw. Spalte ihren Platz mind. einmal wechselt.
Thorsten, kannst du deinen Java-Code mal veröffentlichen? Würde mich sehr interessieren, wie das aufgebaut ist.
Grüße
|
|
baka0815
      
Beiträge: 489
Erhaltene Danke: 14
Win 10, Win 8, Debian GNU/Linux
Delphi 10.1 Berlin, Java, C#
|
Verfasst: Di 02.12.08 14:32
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 02.12.08 15:49
Hallo,
@freedy:
Wenn Du Dir in screenShot _5.gif die dritte Zeile anschaust, siehst Du das spätestens in Spalte 3 die 1 hätte gesetzt werden müssen, weil in letzten beiden Spalte die 1 schon vorkommt.
Bei 1000 Zeilen und der Verarbeitung 700.ten Zeile kann es Dir ständig passieren, das irgendwelche Zahlen bis zum Ende schon komplett durch Spalten darüber belegt sind.
Frühestens ab Spalte 1000-700 = 300 könnte eine Zahl in den restlichen folgenden Spalten schon belegt sein.
Ich habe dann einfach die Belegung bei jedem neuerlichem Versagen um eine Spalte früher neu zufällig auswählen lassen, bis ich wieder in der ersten Spalte war.
Jetzt versuche ich dem vorzubeugen, indem ich eine Liste machen indem für jede Zahl die letztmögliche Spalte steht, bis zu der sie gesetzt sein muss.
(Zuerst für alle die letzte Spalte, sobald diese durch I belegt , suchen nach der neuen passenden Spalte ohne I davor)
Das wird die Sache erheblich beschleunigen, statt ständig neu anzusetzen.
Wie oben beschrieben kann es zwischen 10 und 1100 ms dauern, also ein Faktor 100 in der Zeit und das sind bestimmt nicht die größten Ausreißer.
Gruß Horst
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Di 02.12.08 16:30
Hey,
ich häng das Netbeans-Projekt mal an, für alle die kein Netbeans haben hier nochmal der entscheidende Teil des Codes:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56:
| long t = System.currentTimeMillis(); Random rnd = new Random(System.currentTimeMillis()); int[] numbers = new int[n]; for (i=0 ; i<n ; i++) matrix[0][i] = i; int last = n; int tmp; int itmp; // fisher-yates: // erstelle Permutation für erste Zeile: for (i=0 ; i<n ; i++){ tmp = rnd.nextInt(last--); itmp = matrix[0][last]; matrix[0][last] = matrix[0][tmp]; matrix[0][tmp] = itmp; } System.out.println("Erste Zeile erstellt..."); // erstelle Permutation für die erste Spalte: for (i=0 ; i<n ; i++) numbers[i] = i; // wieder fisher-yates: last = n; for (i=0 ; i<n ; i++){ tmp = rnd.nextInt(last--); itmp = numbers[tmp]; numbers[tmp] = numbers[last]; numbers[last] = itmp; } System.out.println("Erste Spate erstellt..."); // jetzt noch ein swap, damit [0][0] stimmt: for (i=0 ; i<n ; i++){ if (numbers[i]==matrix[0][0]){ itmp = numbers[i]; numbers[i] = numbers[0]; numbers[0] = itmp; break; } } for (i=0 ; i<n ; i++) matrix[i][0] = numbers[i]; // fülle jetzt den rest: for (i=1 ; i<n ; i++){ for (j=1 ; j<n ; j++){ matrix[i][j] = (matrix[i][0] + matrix[0][j])%n; } } System.out.println("Rest gefuellt..."); StringBuilder bla = new StringBuilder(); System.out.println("Zeit bis hier: " + (System.currentTimeMillis() - t)); for (i=0 ; i<n ; i++){ for (j=0 ; j<n ; j++){ bla.append(String.format("%3d ", matrix[i][j])); } bla.append("\n"); System.out.println(i); } System.out.println("String erstellt..."); jLabel2.setText("Zeit war: " + (System.currentTimeMillis()-t)+ "ms"); jTextArea1.setText(bla.toString()); |
Der Stringbuilder ist auch nicht schneller, ich habe die Vermutung dass das Problem eher bei der String.Format-Methode liegt...
Einloggen, um Attachments anzusehen!
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 04.12.08 08:25
Hallo,
die Ausgabe in ein Stringgrid dauert bei mir für n=1024 auch 5 s , Dafür belegt das Programm 120 Mb mehr Speicher.
also etwa 12 Byte pro Zelle.
Was mir noch zu deiner Belegung eingefallen ist:
Im Grunde genommen erzeugst du nur die erste Zeile und schreibst deren Verschiebungen in die folgenden Zeilen, die du wieder gemischst hast.
Das heisst, bei dieser Kontruktion ist dei Abfolge der Zahlen immer gleich.
Wenn aalso in der ersten Zeile '...1 2 5 4 ...' steht dies in (fast) allen Zeilen so.
Gruß Horst
|
|
|