Array / Alle Kombinationsmöglichkeiten ausprobieren

[marc.beeh]

Hi,
folgendes Problem: Ich habe in Delphi ein array[1..9,1..9] of smallint Dieses möchte ich nun nacheinander mit allen Kombinationsmöglichkeiten füllen, welche im Bereich der Zahlen 1 bis 9 möglich sind.
Wie könnte ich sowas umsetzen?

[Maximus]

Hallo,

Hab ich das richtig verstanden? Du willst diese Array mit allen Kombinatiosnmöglichekeiten, also 91, 19, 87, 78 usw. füllen?

Dann müsste deine Array aber ein wenig größer sein. Den es sind 9^9 2-stellige Kombinationen möglich.

Und dann kannst eventuell so durchgehen:

Delphi-Quellcode:

var X,Y: Integer;

for X := 1 to ArrayGröße do
  for Y := 1 to ArrayGröße do
   Feld[X, Y] := StrToInt(IntToStr(X) + IntToStr(Y));

MFG
Maximus

[BenjaminH]

   Feld[X, Y] := 10*X + Y; Wäre da schneller.
Ich glaube aber, dass er z.B.
198273645
987123456
haben will..
Oder wie?

Viele Grüße Benjamin

[marc.beeh]

Nein, nicht ganz; ich dachte mir das so:
(Ist jetzt der Einfachheit halber mal bloß ein array[1..3,1..3] - bei mir solls bis 9 gehen)

Code:

1 1 1
1 1 1
1 1 1

1 1 2
1 1 1
1 1 1

1 1 3
1 1 1
1 1 1

1 1 4
1 1 1
1 1 1

...

9 9 9
9 9 9
9 9 9

Es soll also jede Zahl zwischen 1 und 9 in Kombination mit jeder anderen an jeder Stelle in diesem Array gestanden haben.

[Ultimator]

Willst du eventuell Sudokus erstellen (wegen 9x9)?
Weil dazu gibts schon einige Programme mit Quellcode, wenn du dich daran eventuell orientieren willst

//edit Argh, der rote Kasten -.-"
Also eher doch keine Sudokus *g*

[marc.beeh]

Nein, um Sudokus gehts nicht. Ich will einfach ganz stumpf alle möglichen Kombinationen, die sich hier ergeben, berechnen.

[ichbins]

Du weisst schon dass es ziemlich viele Möglichkeiten gibt, dieses (3x3) Quadrat zu füllen?

Insgesammt wärend das

Code:

9^(3*3)

Stück, also 387420489. Die passen nicht in den Arbeitsspeicher. Du müsstest also ein

Delphi-Quellcode:

var
  a:array[1..387420489,1..9] of integer   //machen und so füllen:
  i1,i2,i3,i4,i5,i6,i7,i8,i9:integer;
  pos:int64;
begin
  for i1:=1 to 9 do
    for i2:=1 to 9 do
      for i3:=1 to 9 do
        for i4:=1 to 9 do
          for i5:=1 to 9 do
            for i6:=1 to 9 do
              for i7:=1 to 9 do
                for i8:=1 to 9 do
                  for i9:=1 to 9 do
                  begin
                    inc(pos);
                    a[pos,1]:=i1; 
                    a[pos,2]:=i2; 
                    a[pos,3]:=i3; 
                    a[pos,4]:=i4; 
                    a[pos,5]:=i5; 
                    a[pos,6]:=i6; 
                    a[pos,7]:=i7; 
                    a[pos,8]:=i8; 
                    a[pos,9]:=i9; 
                  end; 
end;

kleine Größenrerchnung: Jedes Array-Element hat 9 Elemente zu je 4 byte (integer) -> 36 Byte. Dein Array beansprucht also 13947137604 Byte Arbeitsspeicher. Das sind 12,99 GB. Wenn du den Arraytypen statt Integer zu einem Byte machst, sind es immer noch 4,25 GB. Du musst also noch etwas warten bevor du diese Operation durchführen kannst, aber in 5 Jahren ist so viel Speicher kein Problem mehr.

Bei einem 9x9-Quadrat steigt die Anzahl ins Unermessliche:
9^(9*9) * 36 Bytes = 65900000000000000000000000000000000000000000000000 00000000000000000000 Gigabyte RAM...

[Khabarakh]

Wer hat denn gesagt, dass alle Möglichkeiten gleichzeitig im Speicher vorhanden sein müssen? Ich habe das so verstanden, dass er einfach das Array mit jeder Möglichkeit jeweils einmal braucht. Beim Bruteforcing wird ja auch nicht jede Kombination gespeichert.

[ichbins]

ja, aber ich wette, seine CPU schafft es nicht, alle 10^67 Möglichkeiten innerhalb von einem Jahrhundert durchzuerechnen.

Angenommen er hat ein Mulit-CPU-System mit 4 Wassergekühlten, auf 8GHz getakteten 10-kernigen Cell-Prozessoren. Dieses System wäre etwa 100 x schneller als meines. Auf meinem System dauert das 3x3-Beispiel 2 sec, auf seinem also 0,02 sec. Das 9x9-Beispiel benötigt 5,075287860564156007197541597417e+68 mal so viele Rechenoperationen, es dauert also 1,0150575721128312014395083194834e+67 Sekunden oder 3,2165893972042395014559971428273e+59 Jahre. Da ich davon ausgehen kann, dass nach dieser Zeitspanne bereits jede Art von Materie im Universum (ausser Schwarzen Löchern, die dauern 10^80 Jahre) zerfallen ist, kann ich davon ausgehen, dass es mit heutigen Mitteln unmöglich ist, alle Kombinationen durchzurechnen.

[ichbins]

Falls du es dennoch versuchen willst:

Delphi-Quellcode:

procedure resultready(x,y:integer;result:array of integer);
var
  a:array of array of integer;
  i,j:integer;
  text:string;
begin
  setlength(a,x,y);
  for i:=0 to length(result)-1 do
    a[i div x,i mod x]:=result[i];
  // Jetzt ist in a das Quadrat gespeichert. a[0,0] ruft die linke obere Ecke ab.
  // a[x-1,y-1] ruft die rechte untere Ecke ab.
  for i:=0 to x-1 do begin
    text:=text+#13'|';
    for j:=0 to y-1 do
      text:=text+inttostr(a[i,j])+'|';
  end;
  showmessage('got result:'#13+text);  
end;

procedure dynamicalfor(x,y,calls,reps:integer;params:array of integer);
var
  paramsnew:array of integer;
  i:integer;
begin
  if calls>0 then begin
    setlength(paramsnew,length(params)+1);
    for i:=0 to length(params)-1 do
      paramsnew[i]:=params[i];
    for i:=1 to reps do begin
      paramsnew[length(paramsnew)-1]:=i;
      dynamicalfor(x,y,calls-1,reps,paramsnew);
    end;
  end else begin
    resultready(x,y,params);
  end;
end;

procedure startcall(x,y,zahlenmoeglichkeiten:integer);
var
  a:array of integer;
begin
  setlength(a,0);
  dynamicalfor(x,y,x*y,zahlenmoeglichkeiten,a);
end;

der Vorgang wird mit der Funktion startcall gestartet. In resultready können dann die einzelnen Ergebinsse verarbeitet werden. Über x/y wird die Rechtecksgröße angegeben, in deinem Fall also 9 und 9. In zahlenmöglichkeiten wird die Anzahl der Zahlen angegeben, di e eingesetzt werden. Bei dir sind das 1-9, also heisst es 9.

hm... der algo funzt nicht so... weiss jemand warum? [edit]mit dem neuen Code funktioniert's jetzt[/edit]

Diese rekursive Methode ist etwa 100 mal langsamer als die, die ich oben beschrieben habe, aber dafür kann sie für jede Zahl verwendet werden.