| 
| Autor | Beitrag |  
| Horst_H 
          Beiträge: 1654
 Erhaltene Danke: 244
 
 WIN10,PuppyLinux
 FreePascal,Lazarus
 
 | 
Verfasst: Mo 01.12.08 13:53 
 
Hallo,
 bei welchem n x n ?? n = 5??
 
 
 Gruß Horst
 |  |  |  
| Thorsten83 
          Beiträge: 191
 Erhaltene Danke: 1
 
 
 
 
 | 
Verfasst: Mo 01.12.08 14:21 
 
ups, ja   |  |  |  
| Horst_H 
          Beiträge: 1654
 Erhaltene Danke: 244
 
 WIN10,PuppyLinux
 FreePascal,Lazarus
 
 | 
Verfasst: Mo 01.12.08 14: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 14: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 14: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 14: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 15:16 
 
Ne, nimm folgende Anfangsbelegung:
 		                       Quelltext 
 									| 1:2:
 3:
 4:
 
 | 0  1  2  31  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 15: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 18: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 20: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 11: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: 19326
 Erhaltene Danke: 1749
 
 W11 x64 (Chrome, Edge)
 Delphi 12 Pro, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
 
 | 
Verfasst: Di 02.12.08 12: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 12: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 13: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 13:32 
 |  |  |  
| Horst_H 
          Beiträge: 1654
 Erhaltene Danke: 244
 
 WIN10,PuppyLinux
 FreePascal,Lazarus
 
 | 
Verfasst: Di 02.12.08 14: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 15: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 07: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
 |  |  |  |