Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Multiplikative Partition
Mathematiker - Mi 28.05.14 08:28
Titel: Multiplikative Partition
Hallo,
zur Ablenkung vom stündlichen Kontrollieren des stetig steigenden Wassers in meinem Bach (jedes Jahr Ende Mai das gleiche "Spiel", bis jetzt noch kein Wasser im Haus), d.h. eine durchgemachte Nacht, habe ich mir ein kleines Problem gesucht.
Unter
http://de.wikipedia.org/wiki/Multiplikative_Partition wurde vor wenigen Tagen die "multiplikative Partition" vorgestellt.
Konkret, werden verschiedene Zerlegungen einer Zahl in ein Produkt ihrer Teiler gesucht. Mein Ziel war es, alle diese Partitionen für eine Zahl zu berechnen.
Meine rekursive Lösung funktioniert ganz gut, d.h. sie liefert richtige Ergebnisse, aber bei Zahlen mit schon relativ wenig Teilern kann die Berechnungszeit stark ansteigen. Insbesondere geschieht dies, wenn viele Produktdarstellungen entstehen, die gleiche Faktoren beinhalten.
Während eine 840 in 55 ms gelöst wird, braucht das Programm für 960 schon 3,6 s. Und die Zweierpotenzen sind besonders "bösartig": 128 ... 110 ms, 256 ... 1,2 s und 512 ... 14,5 s?!
Mein Algorithmus geht so vor, dass zuerst von einer Zahl alle Teiler bestimmt werden. Tückisch ist, dass ich kleine Teiler mehrfach benötige, wenn sie auch mehrfach in der Zahl enthalten sind.
Dann wird für jeden Teiler die Zahl mit diesem geteilt und für die Restzahl das "Spiel" rekursiv wiederholt, bis nur noch eine Primzahl übrig bleibt.
Das Umschreiben eines Algorithmus für klassische, also additive, Partitionen habe ich nicht hinbekommen. Wird wahrscheinlich auch keine Lösung sein.
Sieht jemand eine Möglichkeit, dem Programm einen entscheidenden Schubs zu geben, so dass in vertretbarer Zeit auch problematische Zahlen, wie z.B. die 1920 (54,6 s), berechnet werden können.
Danke und beste Grüße
Mathematiker
PS.: Sch..., es schüttet schon wieder aus Eimern. :motz:
Horst_H - Mi 28.05.14 10:13
Hallo,
wieso werden die Teiler alle immer und immer wieder bestimmt?
Ich würde die Zahl erst komplett in Einzelfaktoren zerlegen
512 in 2|2|2|2|2|2|2|2|2|
Dann kann man doch der Rekursion die Restteiler übergeben.
Mist ich habe gerade 5040 eingegeben -> 35 Sekunden.
30030 in 0,3 Sekunden
Was die Probleme macht sind offensichtlich die Potenzen von Teilern, obwohl die ja eigentlich enorm oft gleiche Zahlen ergeben.
Deshalb sollte man lieber statt
Delphi-Quelltext
1:
| tFaktor = [0..200] of integer; |
ala
http://www.entwickler-ecke.de/viewtopic.php?t=108866&start=0&postorder=asc
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| tFaktorPotenz = record
Faktor,
Potenz : DWord;
end;
tFaktorFeld = array [1..9] of TFaktorPotenz; |
nehmen.Das kann man leichter Uebergeben.
Statt
Delphi-Quelltext
1:
2:
3:
| procedure test(zahl:integer;fnr:integer);
eben
procedure test(zahl:integer;fnr:integer;Restteiler:tFaktorFeld); |
Innerhalb eines Faktors mit der Potenz > 1 sollte man doch eine Regel für die Faktoren finden können.
2^5 Zum Beispiel
Zum Beispiel alle einzeln umklammern,
(2)*(2)*(2)*(2)*(2)
Dann die Einzelklammer jeweils um 1 vergrössern.
(2*2)*(2)*(2)*(2)= 4*2*2*2
(2*2)*(2*2)*(2) = 4*4*2
Dann
(2*2*2)*(2)*(2) = 8*2*2
(2*2*2)*(2*2) = 8*4
Dann
(2*2*2*2)*(2) = 16*2
und schliesslich
(2*2*2*2*2) = 32
Schlussendlich muss man dann "nur" noch eine Permutation der Primfaktoren machen und entsprechend klammern.
Das passt wohl nicht :-(
A*B*C*D
(A*B)*C*D
(A*B)*(C*D)
(A*B*C)*D
(A*B*C*D)
...
A*C*B*D ( fällt weg)
(A*C)*B*D
(A*C*B)*D ( fällt auch weg )
(A*C*B*D) ( fällt auch weg )
Es muss anders gehen..
Gruß Horst
Xion - Mi 28.05.14 13:24
Wie
Horst_H würde auch ich erstmal die Primfaktoren berechnen und diese entsprechend Stapeln, so dass du für 1280 die Tupel ( 2,8 ) und (5,1) hast.
Dann nimmst du einfach deinen Algorithmus mit einer kleinen Erweiterung:
Zur 1280 merkst du dir erstmal (8,1), du kannst also 8x durch 2 teilen und 1x durch 5. Dann teilst du 1280 einmal durch 2 und einmal durch 5. Welche 2 du benutzt, ist dabei ja völlig egal. Du erhälst dann 640 (7,1) und 256 (8,0). Ok, an diesem Beispiel sieht man schon, dass 256 nun nur noch durch 2 geteilt werden kann. Nach 8 Rekursionen ist die 256 also fertig zerlegt. Die Primfaktorzerlegung hast du auch für jede berechnete Zahl automatisch gegeben. Was du dadurch erhälst ist ein
Hasse-Diagramm [
http://www.win.tue.nl/ida/demo/c1s1ja.html].
Zahlen, welche die gleiche Zerlegung haben (d.h. auch die gleiche Zahl sind) kannst du per Hashtabelle z.B. aufspüren, so dass du nicht 1280/5/2... und 1280/2/5... rechnen musst, wobei ja jedesmal das selbe herauskommt.
Zusammen mit deinem bisherigen Algorithmus zur Bestimmung der Partitionen sollte das recht schnell gehen.
Horst_H - Mi 28.05.14 13:30
Hallo,
kann es sein, dass es zum Großteil nur an der Stringverarbeitung liegt???.
Ich habe mal s als String[80], also shortstring definiert ( uniquestring sozusagen ).Zudenm habe ich die Liste Sortiert gelassen und dupIgnore gesetzt, also werden doppelte nicht eingefügt.
Es ist dadurch für 1920 in 11.9 statt 115 Sekunden (bei mir ) fertig.
Delphi-Quelltext
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:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
| procedure TForm1.Button1Click(Sender: TObject);
type
tfaktor = array[1..64] of integer;
var
zahl:integer;
liste:tstringlist;
faktoren,faktoren2 : tfaktor;
t1x,t2x,frequenz : TLargeInteger;
procedure test(zahl:integer;fnr:integer);
var i,j,
zahl2,nr,wurzel,hilf:integer;
teilermenge: tfaktor;
s:string[80];
begin
teilermenge[1]:=zahl;
if (not isprim(zahl)) then
begin
wurzel:=trunc(sqrt(zahl)+0.5);
nr:=2;
for i:=2 to wurzel do
begin
if zahl mod i = 0 then
begin
teilermenge[nr]:=i;
inc(nr);
zahl2:=zahl div i;
while zahl2 mod i = 0 do
begin
teilermenge[nr]:=i;
zahl2:=zahl2 div i;
inc(nr);
end;
teilermenge[nr]:=zahl div i;
inc(nr);
end;
end;
dec(nr);
for i:=1 to nr-1 do
for j:=i+1 to nr do
begin
if teilermenge[i]<teilermenge[j] then
begin
hilf:=teilermenge[i];
teilermenge[i]:=teilermenge[j];
teilermenge[j]:=hilf;
end;
end;
if nr>1 then
begin
for i:=1 to nr do
begin
faktoren[fnr]:=teilermenge[i];
if zahl<>teilermenge[i] then
test(zahl div teilermenge[i],fnr+1)
end;
end
end;
if teilermenge[1]>1 then
faktoren[fnr]:=teilermenge[1]
else
dec(fnr);
faktoren2:=faktoren;
for i:=1 to fnr-1 do
for j:=i+1 to fnr do
begin
if faktoren2[i]<faktoren2[j] then
begin
hilf:=faktoren2[i];
faktoren2[i]:=faktoren2[j];
faktoren2[j]:=hilf;
end;
end;
s:='';
for j:=1 to fnr do
s:=s+Format('%.4d;',[faktoren2[j]]);
liste.add(s);
end;
begin
QueryPerformanceFrequency (frequenz); QueryPerformanceCounter (t1x);
liste:=tstringlist.create;
liste.sorted:= true;
liste.Duplicates:=dupignore;
zahl:=strtoint(edit1.text);
test(zahl,1);
listbox1.items.assign(liste);
liste.free;
label3.caption:=inttostr(listbox1.items.count);
QueryPerformanceCounter (t2x); if (t2x-t1x)>frequenz then
label5.caption:=FormatFloat('0.0 s',(t2x-t1x)/frequenz)
else
label5.caption:=FormatFloat('0.0 ms',1000*(t2x-t1x)/frequenz);
end; |
Ich hatte mal versucht nur durch Primzahlen zu teilen, aber dabei gehen manche Zahlen unter.
Bei 1920 habe ich statt 165 Varianten nur 160. ( 640*3 kommt zum Beispiel nicht vor ).
Also muss ich dass mit der Faktorenliste, die Übergeben wird überdenken.
Wenn einmal das durchzieht, alle Teiler zu finden.
AlleTeiler( 30) = (30,15,10,6,5,3,2,1)
Dann kann der Rest= 30 div AlleTeiler(?) auch nur Teiler aus AlleTeiler haben.
Damit muss ich dann nicht mehr alle Zahlen <= Rest /2 untersuchen, sondern nur aus AlleTeiler <= Rest /2
Gerade bei 1920 und 2 mit Rest 960 wäre das günstig ;-)
//Mit einer Memo statt Listbox bekommt man es auch kopiert...
AlleTeiler(1920)= 1920;960;640;480;384;320;240;192;160;128;120;96;80;64;60;48;40;32;30;24;20;16;15;12;10;8;6;5;4;3;2;
Sehe gerade Hasse Diagramm nach ;-) ...
Gruß Horst.
Gammatester - Mi 28.05.14 14:05
Horst_H hat folgendes geschrieben  : |
Hallo,
kann es sein, dass es zum Großteil nur an der Stringverarbeitung liegt???.
Ich habe mal s als String[80], also shortstring definiert ( uniquestring sozusagen ).Zudenm habe ich die Liste Sortiert gelassen und dupIgnore gesetzt, also werden doppelte nicht eingefügt.
Es ist dadurch für 1920 in 11.9 statt 115 Sekunden (bei mir ) fertig.
|
Da zeigt zumindest die Richtung: Dramatisch wird der Effekt, wenn man versuchsweise vor //Ausgabe ein exit setzt und dadurch die Ausgabe ganz aushebelt. Für 5040 sind's dann bei mir ca 50ms für 1920 ca 400 ms.
Horst_H - Mi 28.05.14 15:30
Hallo,
ich habe ein Memo statt ListBox genommen.
Dann wie oben beschrieben nur mit den möglichen Teilern geteilt, die entstehende Liste ist übrigens automatisch sortiert.
Das beschleunigt die Sache ein wenig ;-)
1920 Laufzeit: 1.Durchgang 50 ms -> danach 18 ms
tFaktoren habe ich bei 1..200 gelassen.
485100 ( 210 (=2*3*5*7)*210 *11 ) hat schon 160
Laufzeit: 1.Durchgang 6.3s -> danach 5.5 s
Delphi-Quelltext
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:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
| unit umulfaktor;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;
type
tfaktor = array[1..200] of integer;
TForm1 = class(TForm)
Edit1: TEdit;
Button1: TButton;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
private
liste:tstringlist;
fAlleTeiler :tfaktor;
faktoren,faktoren2 : tfaktor;
s: string[255];
fAlleTeilerCnt : integer;
procedure Test(zahl:integer;fnr:integer);
public
end;
var
Form1: TForm1;
implementation
{$R *.DFM}
procedure TForm1.test(zahl:integer;fnr:integer);
var i,j,
zahl2,nr,wurzel,hilf:integer;
teilermenge: tfaktor;
begin
teilermenge[1]:=zahl;
begin
nr:=2;
i := fAlleTeilercnt;
while sqr(fAlleTeiler[i]) > Zahl do
dec(i);
for i:=i downto 1 do
begin
if zahl mod fAlleTeiler[i] = 0 then
begin
teilermenge[nr]:=fAlleTeiler[i];
inc(nr);
end;
end;
dec(nr);
if nr>1 then
begin
for i:=1 to nr do
begin
faktoren[fnr]:=teilermenge[i];
if zahl<>teilermenge[i] then
test(zahl div teilermenge[i],fnr+1)
end;
end
end;
if teilermenge[1]>1 then
faktoren[fnr]:=teilermenge[1]
else
dec(fnr);
faktoren2:=faktoren;
for i:=1 to fnr-1 do
for j:=i+1 to fnr do
begin
if faktoren2[i]<faktoren2[j] then
begin
hilf:=faktoren2[i];
faktoren2[i]:=faktoren2[j];
faktoren2[j]:=hilf;
end;
end;
s:='';
for j:=1 to fnr do
s:=s+Format('%.6d;',[faktoren2[j]]);
liste.add(s);
end;
procedure TForm1.Button1Click(Sender: TObject);
var
zahl,i,j:integer;
t1x,t2x,frequenz : TLargeInteger;
s:AnsiString;
begin
liste:=tstringlist.create;
liste.sorted:= true;
liste.Duplicates:=dupignore;
zahl:=strtoint(edit1.text);
QueryPerformanceFrequency (frequenz); QueryPerformanceCounter (t1x);
fAlleTeilerCnt := 1;
For i := 2 to Zahl do
begin
IF Zahl MOD i = 0 then
Begin
fAlleTeiler[fAlleTeilerCnt] := i;
inc(fAlleTeilerCnt);
end;
if sqr(i)>=Zahl then
break;
end;
dec(fAlleTeilerCnt);
i := fAlleTeilerCnt;
IF fAlleTeiler[i] = (Zahl div fAlleTeiler[i]) then
dec(i);
For i := i downto 1 do
begin
inc(fAlleTeilerCnt);
fAlleTeiler[fAlleTeilerCnt] := Zahl div fAlleTeiler[i];
end;
test(zahl,1);
liste.sorted:= false;
liste.Add('Anzahl Teiler '+IntToStr(fAlleTeilerCnt));
Memo1.lines.assign(liste);
liste.free;
label3.caption:=inttostr(memo1.lines.count-1);
QueryPerformanceCounter (t2x); if (t2x-t1x)>frequenz then
label5.caption:=FormatFloat('0.0 s',(t2x-t1x)/frequenz)
else
label5.caption:=FormatFloat('0.0 ms',1000*(t2x-t1x)/frequenz);
end; |
Gruß Horst
Mathematiker - Mi 28.05.14 15:33
Hallo,
Danke an Horst_H, Xion und Gammatester. Ich werde mir Eure Vorschläge sofort ansehen.
Die immer wiederholte Berechnung der Teiler war wohl das größte Problem. Mal sehen, wie schnell es bei mir wird.
Nochmals Danke und beste Grüße
Mathematiker
Nachtrag: Wow, das muss ich erst einmal verdauen. Die 1920 braucht bei mir nur noch 27 ms. Das ist 2000mal schneller.
Danke!
Horst_H, ich bin extrem beeindruckt.
Die Idee, am Anfang alle Teiler zu bestimmen und dann die entsprechenden auszuwählen, ist sehr gut. Das beschleunigt richtig. Und damit fällt auch die Sortiererei weg. Sehr schön.
Bei meinem Delphi 5 ist die Verwendung von string an Stelle von string[255] noch etwas schneller.
Horst_H - Mi 28.05.14 18:16
Hallo,
ohne Ausgabe ist es wesentlich schneller, aber es kommen doppelte vor, weshalb ja auch die faktoren2 sortiert werden und die Stringliste sortiert ohne doppelte ist.
Das muss doch noch besser gehen (Faktor 2000 wird es nicht mehr ;-) )
Die Faktoren müssten immer noch sortiert werden, da ein HashWert nur bei Sortierung etwas sinnvolles ergibt.
Auch wenn es 79(+2 für die Eins und sich selbst) verschiedene Teiler von 44100= 7*7*5*5*3*3*2*2 gibt, kann es maximal 8 Faktoren geben.
Das hilft nicht, am Ende werden ja immer alle benutzt.
Man könnte ja eine Menge/set der TeilerNr nehmen in denen die Verwendung von welchen Teilers aus AlleTeiler markiert ist.
Im Falle von 44100= 49*25*9*4 könnten eben diese Teiler markiert sein
Anzahl Partitionen 712 ( << 8!= 40320 )
Anzahl Teiler 79
Teiler 22050;14700;11025;8820;7350;6300;4900;4410;3675;3150;2940;
2450;2205;2100;1764;1575;1470;1260;1225;1050;980;900;882;735;700;
630;588;525;490;450;441;420;350;315;300;294;252;245;225;210;196;180;
175;150;147;140;126;105;100;98;90;84;75;70;63;60;50;49;45;42;36;35;
30;28;25;21;20;18;15;14;12;10;9;7;6;5;4;3;2;
Dazu müsste man zusätzlich zum Teiler auch dessen Nr speichern, dann könnte man dieses set leicht parallel in der Rekursion pflegen,
Statt Ausgabe, würde man diese Menge in einer Liste aufnehmen, falls es nicht schon vorkommt ( HashWert über das set bilden).
485100 hat 160 Teiler und es dauert mit Stringliste und Entfernung der doppelten 5.5 Sekunden ohne 0,4 s
Nachher sortieren und entfernen dauert erheblich länger.
Gruß Horst
Mathematiker - Mi 28.05.14 21:10
Hallo,
ich habe darüber nachgedacht, das Problem völlig anders anzugehen.
Ausgehend von der Primfaktorzerlegung, bei Deinem Beispiel 44100= 7*7*5*5*3*3*2*2, könnte man alle Kombinationen der 8 Faktoren zu k = 1 bis 8 ausgewählte Faktoren testen. Das wären im Beispiel insgesamt 2^8 = 256 Produkte.
Das dürfte schneller gehen.
Nur leider: Mir fehlt noch die Idee (der Algorithmus), wie man aus insgesamt n Faktoren alle möglichen Paare, Tripel, ..., n-Tupel auswählt.
Konkret gesagt, wie berechnet man alle Kombinationen von k aus n ausgewählten Elementen?
Beste Grüße
Mathematiker
Horst_H - Mi 28.05.14 22:12
Hallo,
So selbstbezogen, wie ich bin:
http://www.entwickler-ecke.de/viewtopic.php?t=74423&postorder=asc&start=40
es gibt für 44100= 7*7*5*5*3*3*2*2 genau 2520 Kombinationen die 2,3,5,7 zu verteilen.
Aber:
Jetzt müssen Klammern gesetzt werden, um die einzelnen Faktoren zu bestimmen.
Wieviel Klammern kann man da unterschiedlich setzen, bei 8 Faktoren.
Und das dann 2520 fach.
Die Zahl wird mir zu groß, ich baue mal einen Zähler ein
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| 44100 =7*7*5*5*3*3*2*2
Anzahl Teiler 79
Anzahl Ausgabeaufrufe 20805 ( es also über 20000 doppelte )
Anzahl multiplikativer Partitionen 712
485100 =11*7*7*5*5*3*3*2*2
Anzahl Teiler 160
Anzahl Ausgabeaufrufe 598352 ( es also über 595000 doppelte )
Anzahl multiplikativer Partitionen 3274 |
Dann vielleicht anders.
Wir haben die Tabelle der Teiler.
Jetzt alle Paare suchen, Die stehen ja schon direkt da.
Teiler(n-i)*Teiler(i). Aber eben nur solange n-i> i
dann alle Tripel, Fangen an bei Teiler(k) <= Zahl div (Teiler(1)^2 ( falls Teiler(1) mehrfach vorkommt) bis maximal dritte(Wurzel aus Zahl )
Mist, bei den Tripel müsste man schon die Vielfachheit eines Teilers auch berücksichtigen.
Also statt multiplizieren zu jedem Teiler die Primzahlzerlegung.dann braucht man nur die Exponenten addieren.Wenn die Exponenten in Summe kleiner = Exponenten der Zahl sind gibt es einen Teiler.
Quelltext
1:
2:
3:
4:
5:
6:
7:
| Primfaktor,Anzahl = [7,2]
44100 = [7,2]*[5,2]*[3,2]*[2,2]
Teiler1= [7,1],[5,1],[3,2],[2,0]
Teiler2= [7,1],[5,1],[3,0],[2,0]
bleibt für Teiler 3:
Teiler3= [7,0],[5,0],[3,0],[2,2] |
Vielleicht kan man daraus etwas basteln.
Für Zweier ein Zähler über die Stellen immer Basis-1 = Vielfachheit der Primzahl
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
| 44100 = [7,2]*[5,2]*[3,2]*[2,2]
A 0 0 0 1 2
B 2 2 2 1 22050
A 0 0 0 2 4 // +1
B 2 2 2 0 11025
A 0 0 1 0 3 // +1 Überlauf -> 3
B 2 2 1 2 14700
A 0 0 1 1 6
B 2 2 1 1 7350
...
A 1 1 1 1 210
B 1 1 1 1 210
Nicht weiter, weil Potenzen von A > Potenzen B |
Gruß Horst
Mathematiker - Mi 28.05.14 22:38
Hallo,
Das ist ein interessanter Anfang. Mal sehen, was daraus wird.
Meine obige Rechnung war übrigens falsch, da ich vergessen hatte, das mehrere Klammern auftreten können.
Richtig ist:
Die Bellzahl bezeichnet die Anzahl möglicher Partitionen über eine Menge mit n Elementen.
Es gilt B(n) = Summe von k=1 bis n der {n k}
wobei {n k} die Stirlingsche-Zahl 2.Art ist.
Beispielsweise ist die Bellzahl für eine 3-elementige Menge die 5, da sich die Menge {a,b,c} in folgende 5 Möglichkeiten partitionieren lässt:
1. {a,b,c}; 2. {a,b} und {c}; 3. {a,c} und {b}; 4. {b,c} und {a}; 5. {a} und {b} und {c}.
Die ersten Bell-Zahlen sind
1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, …
Für 8 Primfaktoren gibt es also 4140 Partitionen, von denen natürlich einige, bei gleichen Faktoren, auch gleich sind.
Jetzt heißt es also, alle diese Partitionen zu ermitteln.
Ich werde mal im Netz nach einem Algorithmus suchen, mache mir aber keine große Hoffnung.
Beste Grüße
Mathematiker
Horst_H - Mi 28.05.14 22:55
Hallo,
das Programm tut es wohl.
Wenn man als Zahl nur solche mit Faktoren der Potenz 1 benutzt wie 510510 = 2*3*5*7*11*13*17 kommt auch 877 als Lösung heraus, bei Anzahl Ausgabeaufrufe= 47556 Nicht so prickelnd.
Genug jetzt.
Gruß Horst
Hidden - Mi 28.05.14 23:16
Hallo,
das Problem unterteilt sich doch in zwei Teile:
a) Primfaktorzerlegung, wir erhalten ein
n-Tupel mit den Prim-Teilern. (Entsprechend ihrer Vielfachheit sind diese eventuell mehrfach enthalten.)
sowie
b) Zusammensetzen aller möglichen Kombinationen dieser Teiler.
(Was mir noch nicht klar ist: kommt die Eins in einem Segment jeder Partition jeder Zahl vor, oder ist sie ausgenommen? Im Folgenden werde ich letzteres annehmen.)
--
Wir wollen Bitmasken verwenden um zu kodieren, welche Teiler des Tupels in einem Segment enthalten sind. Um mehrere Segmente zu einer Partition zusammenzusetzen, muss jedes Bit der Maske in genau einem Segment gesetzt sein.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
| Zahl: 42
Primfaktorzerlegung: 2 * 3 * 7
Zerlegungeg 1:
1 1 1 (Bitmaske: 7)
Zerlegung 2:
1 1 0 (Bitmaske: 6)
0 0 1 (Bitmaske: 1)
Zerlegung 3:
1 0 1 (Bitmaske: 5)
0 1 0 (Bitmaske: 2)
Zerlegung 4:
1 0 0 (Bitmaske: 4)
0 1 1 (Bitmaske: 3)
Zerlegung 5:
1 0 0 (Bitmaske: 4)
0 1 0 (Bitmaske: 2)
0 0 1 (Bitmaske: 1) |
Wie man sieht, lässt sich jeder Multiplikativ-Zerlegung einer Zahl mit
n Teilern eine Additiv-Zerlegung der Zahl
2^n - 1 zuordnen. Diese Zuordnung ist
eineindeutig leider nicht surjektiv.
Grüße,
Daniel
Mathematiker - Mi 28.05.14 23:22
Hallo,
| Hidden hat folgendes geschrieben : |
| Wie man sieht, lässt sich jeder Multiplikativ-Zerlegung einer Zahl mit n Teilern eine Additiv-Zerlegung der Zahl 2^n - 1 zuordnen. Diese Zuordnung ist eineindeutig, das die betreffenden Mengen sind isomorph. |
Das klingt interessant. Die Frage ist nun "nur", wie setzt man das in einen schnellen Algorithmus um.
Ich werde darüber nachdenken.
Jetzt muss ich aber erst einmal ins Bett. Schlaf nachholen.
Beste Grüße
Mathematiker
Hidden - Mi 28.05.14 23:33
| Mathematiker hat folgendes geschrieben : |
Die Frage ist nun "nur", wie setzt man das in einen schnellen Algorithmus um.
Ich werde darüber nachdenken.
Jetzt muss ich aber erst einmal ins Bett. Schlaf nachholen. |
Schlaf ist immer gut :zustimm:
.. und ich hätte auch nochmal drüber Schlafen sollen: Das war Quatsch, die Zuordnung ist nicht surjektiv; Zerlegungen wie 2 + 2 + 2 + 1 = 7 werden nicht getroffen.
Edit: Noch ein Versuch. Die Mul-Partitionen einer Zahl mit
n Teilern sind isomorph zu den
Partitionen der Menge [
http://de.wikipedia.org/wiki/Partition_%28Mengenlehre%29]
\{1, \ldots, n\}. Nicht weiter spektakulär, aber immerhin etwas das schon erforscht ist.
Edit2: Partition_(Mengenlehre) verlinkt auf Bellsche_Zahl, verlinkt auf Multiplikative_Partitionen. Und der Kreis schließt sich :lol:
beste Grüße zurück,
Daniel
Xion - Do 29.05.14 01:05
| Mathematiker hat folgendes geschrieben : |
| Das klingt interessant. Die Frage ist nun "nur", wie setzt man das in einen schnellen Algorithmus um. |
Das Problem ist, dass bei diesem Verfahren bei vielen gleichen Faktoren die selbe Zerlegung mehrfach berechnet wird, z.B.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| 160 = 2^5 * 5
1 0 0 0 0 0 = 2
0 1 1 1 1 1 = 80
0 0 0 1 0 0 = 2
1 1 1 0 1 1 = 80
0 1 1 1 1 1 = 80
1 0 0 0 0 0 = 2
... |
Dem könnte man Abhilfe schaffen, indem man statt Bitstrings Vielfachheiten benutzt
Quelltext
1:
2:
| 1 0 = 2
5 1 = 2^5 * 5^1 = 80 |
Wenn die dann noch lexikographisch geordnet sind (1 0 vor 5 1), dann ist die Zerlegung eindeutig kodiert. Bleibt aber die Frage, wie man nun alle Kodierungen aufzählt. Intuitiv irgendwie mit dynamischer Programmierung...
Mathematiker - Do 29.05.14 07:21
Hallo,
macht Euch keinen Stress!
Ich muss mich leider bis Sonntag Nachmittag hier "abmelden". Also bitte nicht sauer sein, wenn ich auf Eure Beiträge nicht gleich reagiere.
Beste Grüße
Mathematiker
Horst_H - Do 29.05.14 10:07
Hallo,
Die Primfaktorzerlegung als Zahl aufzufassen hat den enormen Vorteil, das man nicht gegen Strings vergleichen muss, sondern in eine Zahl umrechnen kann.
Bei
http://de.wikipedia.org/wiki/Bellsche_Zahl Bellsche Zahl sogar als Bits also zweier Potenzen.
Alles schön und gut, aber wie beschleunigt man die Bestimmung der richtigen Anordnung?
Ich dachte schon mal so:
Wenn ich zwei Faktoren haben aus n-Bits bestimme, hat der eine k Bits gesetzt und der andere (n-k);
Also jeweils n über k Anordnungen sind möglich , k=n fällt weg (Produkt wäre 0 )
Für Zwei Faktoren habe ich dann Summe (k = n-1 bis n/2 ) (n über k)
Für drei Faktoren, würde ich einen abspalten, den Rest an 2 Faktoren übergeben.
Dabei kann ich für den ersten Faktor aus n bits 1 ( 1 aus n == n über 1 ), 2( 2 aus n) ,3,4 .. n-2 Bits nutzen
Daraus werden dann 2 Faktoren aus n-1 bis hinab zu 2 Bits bestimmt.
Welche Primzahl eine Bitposition aber repräsentiert ist völlig frei. Bit 0 könnte für 2 oder 3 oder 127 stehen.
001 für z= 30 ( n=3 ) mit 2*3*5 könnte 2,3 oder 5 heißen.
Was ich erreichen will, ist , dass eine Abspaltung eines Faktors nur einmal das oberste Bit betrifft oder die obersten beiden etc.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| Das Ergebnis wäre dann für 3 Faktoren
n-Bit n-1 bit ist komplementär
Faktor 1 1 Bit = immer 01111..111-> Faktor 2 = 0111..11 Faktor 3 = 1000..00
-> Faktor 2 = 0011..11 Faktor 3 = 1100..00
-> Faktor 2 = 0001..11 Faktor 3 = 1110..00
...
-> Faktor 2 = 0000..01 Faktor 3 = 1111..10
n-Bit n-2 bit
Faktor 1 2 Bit = immer 00111..111 |
Dummerweise bleibt das Problem 5x3 = 3x5.Auch im Umbennen bin ich nicht frei.
Was aber, wenn ich die Ordnung der Primzahlen bei Entnahme dann doch sortiert lasse?.
n= 3 Primzahlen, ich nemhe mal [5,3,2] und Aufteilung in zwei Faktoren.
Ich hätte dann
001 x 110 ( 1 kann jetzt 5,3,2 sein) dann ist 110
Erst 5 entnehmen, feld um eine kürzen
[5] x[3,2] Menge als Feld ansehen:Erst 3 entnehmen, dann Folgeelement = 2
[5] x[3,2]- Menge als Feld ansehen:Erst 2 entnehmen, dann Folgeelement = [] - wegfallen lassen
Jetzt 3 entnehmen
[3] x[5,2] Menge als Feld ansehen:Erst 5 entnehmen, dann Folgeelement = 2
[3] x[5,2]-Nächsten in der Menge probieren:Erst 2 entnehmen, dann Folgeelement = [] - wegfallen lassen
das selbe mit 2
[2] x[5,3] Menge als Feld ansehen:Erst 5 entnehmen, dann Folgeelement = 3
[2] x[5,3]-Nächsten in der Menge probieren:Erst 2 entnehmen, dann Folgeelement = [] - wegfallen lassen
Also bleiben 5 x 6 und 3x 10 sowie 2 *15 übrig.
Das mag für Mengen Partitionen, in denen alle Elemente verschieden sind, gelten. Aber bei Mehrfachen wird das wieder schwierig.
Was red ich, erst mal testen ob das so funktioniert.
Gruß Horst
Xion - Do 29.05.14 10:49
Ich hätte da noch eine Idee bzgl des Hasse-Diagramms, die vom grundlegenden Zeitaufwand optimal sein sollte:
1. Primfaktoren bestimmen und der Größe nach sortieren.
Beispiel:
216 = 2^3 * 3^3 -> (3,3 = 216)
2. Knoten des Hasse-Diagramm aufbauen und Knoten nach Größe sortieren.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| (3,3 = 216)
(2,3 = 108)
(3,2 = 72)
(1,3 = 54)
(2,2 = 36)
(3,1 = 24)
(1,2 = 18)
(2,1 = 12)
(0,2 = 9)
(1,1 = 6)
(2,0 = 4)
(0,1 = 3)
(1,0 = 2) |
3. Rekursion starten: Ausgangszahl durch jede Zahl im Hasse-Diagramm teilen bis hin zu
größten Primzahl
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
| (3,3 = 216)/(3,3 = 216) = (0,0 = 1) -> Lösung: 216*1
(3,3 = 216)/(2,3 = 108) = (1,0 = 2) -> Lösung: 108*2
(3,3 = 216)/(3,2 = 72) = (0,1 = 3) -> Lösung: 72*3
(3,3 = 216)/(1,3 = 54) = (2,0 = 4) -> Lösung: 54*...
(3,3 = 216)/(2,2 = 36) = (1,1 = 6) -> Lösung: 36*...
(3,3 = 216)/(3,1 = 24) = (0,2 = 9) -> Lösung: 24*...
(3,3 = 216)/(1,2 = 18) = (2,1 = 12) -> Lösung: 18*...
(3,3 = 216)/(2,1 = 12) = (1,2 = 18) -> Lösung: 12*...
(3,3 = 216)/(0,2 = 9) = (3,1 = 24) -> Lösung: 9*...
(3,3 = 216)/(1,1 = 6) = (2,2 = 36) -> Lösung: 6*...
(3,3 = 216)/(2,0 = 4) = (1,3 = 54) -> Lösung: 4*...
(3,3 = 216)/(0,1 = 3) = (3,2) = 72) -> Lösung: 3*...
(3,3 = 216)/(1,0 = 2) Abbruch, 3 größte Primzahl in (3,3) |
Die Idee dabei: wir erzeugen nur nach Größe der Faktoren sortierte Zerlegungen. Das ist (nahezu?) eindeutig. Man muss außerdem nichts Teilen und auch keine Werte mehr multiplizieren, da man einfach die Primzahl-Tupel subtrahiert.
4. Rekursives Teilen, aber jeweils nur durch Knoten im Hasse-Diagramm teilen, die kleinergleich dem letzten Faktor ist.
Beispiel:
(2,1 = 12) hatte bereits den Faktor 18*
Also: Teilen durch alle Knoten <=18 bis zur größten übrigen Primzahl:
Quelltext
1:
2:
3:
4:
5:
| (2,1 = 12)/(1,2 = 18) -> geht nicht, da nun Primzahlpotenz negativ (1,-1)
(2,1 = 12)/(2,1 = 12) = (0,0 = 1) -> Lösung: 18*12
(2,1 = 12)/(1,1 = 6) = (1,0 = 2) -> Lösung: 18*6*2
(2,1 = 12)/(0,1 = 3) = (2,0 = 4) -> Lösung: 18*3*...
(2,1 = 12)/(1,0 = 2) Abbruch, 3 größte Primzahl in (2,1) |
Jetzt müsste man das nur noch ausprogrammieren :mrgreen:
PS: Sehe grad, das Beispiel ist nicht vollständing da ich Knoten im Hasse-Diagramm vergessen hab. Das sollte der Algorithmus natürlich besser hinkriegen :P
Horst_H - Do 29.05.14 11:50
Hallo,
| Zitat: |
| 2. Knoten des Hasse-Diagramm aufbauen und Knoten nach Größe sortieren. |
Ach, und was macht fAlleTeiler ;-) OK, es läßt Zahl und 1 als Teiler weg.
Es ist schade, dass (1,2) kleiner als (2,1) ist.
Aber es bringt mich auf die Idee, die Rekursion zu ändern.
Diese Probiert ja einfach alles durch.
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| if nr>1 then
begin
for i:=1 to nr do
begin
faktoren[fnr]:=teilermenge[i];
if zahl<>teilermenge[i] then
test(zahl div teilermenge[i],fnr+1)
end;
end
end; |
Mal schauen, was das bringt
Gruß Horst
Edit:
Xion hat schon recht, wenn ich ihn richtig verstanden habe.
So wie ich es jetzt umsetzen möchte.
Zahl = 2*3*5*7 =210
Alleteiler von 210 dazu die Teiler der Teiler.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
| 210|1
105|2 -> 35|3; 21|5;15|7; {und umgekehrt 7|15..3|35 aber die braucht es nicht kommutativ)
070|3
etc..
7|30 -> 7|1
6|35 -> 3|2
5|42 -> 5|1
3|70 -> 3|1
2|105 -> 2|1 |
Man kann jetzt sich einfach durchhangeln
erst 105|2 ausgeben, dann -> 105 in 35|3 aufspalten dann die 35 durch 7*5 ersetzen etc pp.
Dadurch braucht außer dieser Tabellen nichts mehr rechnen.
Da der Sprung 105 - 70 groß ist, habe ich vor, statt der Zahlen deren Nummern im Teilerfeld zu nutzen ( geht schon ganz gut )
Trotzdem bleiben Doppelte
Ich kann über 105 *2 -> 35*3*2
und über 70*3->35*2*3 = 35*3*2
Schlussendlich langen alle bei 7*5*3*2 an :-(
Das ist das eigentlich bremsende.
Das alte Programm braucht jetzt für: 2*3*5*7*11*13*17*19*23 real 0m9.564s
(Fpc2.6.4 unter Linux, i-4330 3,5 Ghz)
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
| Komplett ohne Ausgabe
Zahl 223092870
Anzahl Partitionen 0
Anzahl Versuche 2946299
Anzahl Teiler 511
real 0m0.178s
Die Faktoren werden sortiert, aber kein String gebaut
Zahl 223092870
Anzahl Partitionen 0
Anzahl Versuche 2946299
Anzahl Teiler 511
real 0m0.397s
Die Faktoren werden sortiert und in die Stringliste (sort,dupIgnore) eingefügt.
Zahl 223092870
Anzahl Partitionen 21147
Anzahl Versuche 2946299
Anzahl Teiler 511
real 0m9.564s |
9 Sekunden gehen nur für die Suche des Strings drauf. 3 Mio Anfragen bei 21000 Einträgen
Der Gedanke ist nun, mit den Nummern der Teiler/Faktoren zu arbeiten und diese als Zahlen zu sortieren.
Jetzt fällt mir auf, das man in diesem Beispiel 9 Listen machen könnte, für Strings mit verschiedenen Anzahlen von Faktoren.Dann vergleicht man auch nur Strings die überhaupt ähnlich sein können und am Besten, Die Liste mit den meisten Faktoren hat auch nur einen Eintrag:Das Produkt aller Primzahlfaktoren in Ihrer jeweiligen Vielfachheit. Dieser Eintrag wird am häufigsten gecheckt, vielleicht sollte man den vorher abfangen.Denn der wird immer vollständig verglichen.
Schaun mer mal die 2.te
Horst_H - Sa 31.05.14 16:22
Hallo,
es gibt tatsächlich Video's zu sowas.Ich suchte nach Schröderzahlen == Alle möglichen Klammerungen in der Hoffnung, dass die Bestimmung leichter und Doppelte nicht im Faktor 100 auftreten.
EDIT: Jetzt direkt Hassediagram gesucht:
http://www.youtube.com/watch?v=nD8ErWgj5Ac
Hassediagramme (Teil 1) von Prof. Christian Spannagel an der PH Heidelberg
//Lecture 22 . Enumerative Combinatorics (Federico Ardila)
http://www.youtube.com/watch?v=te9xsrQ6q7U
//( ich habe mal Minute 12 geklickt, Abteilung blindes Huhn ;-) ) da folgt auch die Aufstellung mit Potenzen<> 1. am Beispiel 84=2*2*3*7
Mathematiker und
Xion können sicher sofort was damit anfangen.
Gruß Horst
Xion - Sa 31.05.14 16:55
Er schreibt halt das Hasse-Diagramm auf...finde ich wenig spektakulär, das war bei unsrem Prof. nicht anders (nur auf Deutsch und ohne Kappe :mrgreen: )
| Horst_H hat folgendes geschrieben : |
| Dann nur noch alle Wege bis 84 zählen? |
Aufzählen sollte wie an meinem letzten Beispiel im Hasse-Diagramm ohne Duplikate klappen, indem du jeweils nur durch Faktoren teilst, die kleinergleich den vorherigen Faktoren sind (weil dann sind deine Zerlegungen nach Größe sortiert, da kann es keine Doppelten geben).
Wenn du sie nur zählen willst, dann bestimmt es sich vermutlich aus den Primzahlpotenzen...da müsste man dann mit Kombinatorik ran.
Xion - Sa 31.05.14 21:10
So, hab jetzt meine Idee doch mal ausprogrammiert :lol:
Für den Testdatensatz
2*3*5*7*11*13*17*19*23 erhalte ich folgende Ausgabe:
Eingabezahl: 223092870 (Primzahlfaktoren gegeben)
Knoten im Hassediagramm: 512
Berechnung des Hasse-Diagramms: 0ms
Berechnung des Zerlegung-Baumes: 141ms
21147 Zerlegungen ermittelt
Zerlegungen aufgezählt: 21147 in 115975 Iterationen
Zeitbedarf für Aufzählen: 15ms
Gesamtlaufzeit inklusive Ausgabe in Memo: 1453 ms
Wenn man sie dann noch ausgeben will, kann man das gerne tun (im Code enthalten), aber eigentlich ist das unfassbar unübersichtlich. Eine grafische Baumdarstellung wäre auf jeden Fall zu bevorzugen (entsprechend der Datenstruktur, die mein Programm anlegt).
Als Beweis für die Qualität des Algorithmus bei hohen Potenzen die Werte des Testdatensatzes
2^4*3^4*5^4*7^4
Eingabezahl: 1944810000
Knoten im Hassediagramm: 625
Berechnung des Hasse-Diagramms: 0ms
Berechnung des Zerlegung-Baumes: 2984ms
911838 Zerlegungen ermittelt
Zerlegungen aufgezählt: 911838 in 6950247 Iterationen
Zeitbedarf für Aufzählen: 313ms
und der Testdatensatz
2^{60}
Eingabezahl: 1152921504606846976
Knoten im Hassediagramm: 61
Berechnung des Hasse-Diagramms: 0ms
Berechnung des Zerlegung-Baumes: 625ms
966467 Zerlegungen ermittelt
Zerlegungen aufgezählt: 966467 in 15959618 Iterationen
Zeitbedarf für Aufzählen: 953ms
Abschließend noch der (zugegeben, quick & very dirty) Quellcode, aber ich muss sagen, wenn ich C++ programmiere und mir viel Mühe gebe ist es unübersichtlicher :mrgreen:
Delphi-Quelltext
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:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
| unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Math;
type
TForm1 = class(TForm)
Memo1: TMemo;
procedure FormShow(Sender: TObject);
private
public
end;
type THasseDiagrammKnoten = record
potenz: array of integer;
wert: int64;
end;
type TPartitionTreeNode = record
pred: integer;
faktor: int64;
minHasseIdx: integer;
wertHasseIdx: integer;
end;
const DOLOGGING = true;
PRED_ROOTNODE = -1;
PRED_PRUNEDNODE = -2;
var
Form1: TForm1;
HasseDiagramm: array of THasseDiagrammKnoten;
Primzahl: array of integer;
PartitionenBaum: array of TPartitionTreeNode;
implementation
{$R *.dfm}
procedure TForm1.FormShow(Sender: TObject);
var A,B,C: integer;
potenzProd: array of integer;
i: Int64;
S: String;
time: cardinal;
nextToDo: integer;
nextEmpty: integer;
nextEmptyBuf: integer;
leafCount: integer;
partitionCount: integer;
bitmask: array of boolean;
pred: integer;
fullTime: cardinal;
begin
fullTime := GetTickCount;
Memo1.Visible := false;
SetLength( HasseDiagramm, 1 );
SetLength( HasseDiagramm[0].potenz, 4 );
SetLength( Primzahl, 4);
Primzahl[0] := 2;
HasseDiagramm[0].potenz[0] := 4;
Primzahl[1] := 3;
HasseDiagramm[0].potenz[1] := 4;
Primzahl[2] := 5;
HasseDiagramm[0].potenz[2] := 4;
Primzahl[3] := 7;
HasseDiagramm[0].potenz[3] := 4;
HasseDiagramm[0].wert := 1;
for A:= 0 to High(HasseDiagramm[0].potenz) do
begin
HasseDiagramm[0].wert := HasseDiagramm[0].wert * round( power(primzahl[A], HasseDiagramm[0].potenz[A]) );
end;
Memo1.Lines.Add('--- Eingabezahl: ' + inttostr(HasseDiagramm[0].wert) );
SetLength(potenzProd, Length(HasseDiagramm[0].potenz));
C := 1;
for A:= 0 to High(HasseDiagramm[0].potenz) do
begin
potenzProd[A] := C;
C := C*(HasseDiagramm[0].potenz[A]+1);
end;
Memo1.Lines.Add('--- Knoten im Hassediagramm: ' + inttostr(C) );
time := GetTickCount;
SetLength(HasseDiagramm,C);
for A:= High(HasseDiagramm) downto 0 do
begin
C := A;
SetLength(HasseDiagramm[A].potenz, Length(primzahl));
HasseDiagramm[A].Wert := 1;
for B:= High(Primzahl) downto 0 do
begin
HasseDiagramm[A].potenz[B] := C div potenzProd[B];
C := C mod potenzProd[B];
HasseDiagramm[A].Wert := HasseDiagramm[A].Wert * round(power(Primzahl[B],HasseDiagramm[A].potenz[B]));
end;
end;
time := GetTickCount-time;
if DOLOGGING then
for A:= 0 to High(HasseDiagramm) do
begin
S := '(';
for B:= 0 to High(Primzahl) do
S := S + inttostr(HasseDiagramm[A].potenz[B])+',';
S:= Copy(S, 1, Length(S)-1);
S:= S + ' = '+inttostr(HasseDiagramm[A].wert)+')';
Memo1.Lines.Add(S);
end;
Memo1.Lines.Add('--- Berechnung des Hasse-Diagramms: '+inttostr(time)+'ms');
time := GetTickCount;
SetLength(PartitionenBaum,1);
PartitionenBaum[0].minHasseIdx := High(HasseDiagramm); PartitionenBaum[0].faktor := 1;
PartitionenBaum[0].pred := PRED_ROOTNODE; PartitionenBaum[0].wertHasseIdx := High(HasseDiagramm);
nextToDo := 0;
nextEmpty := 1;
while nextToDo < nextEmpty do
begin
if High(PartitionenBaum) < nextEmpty + PartitionenBaum[nextToDo].minHasseIdx + 1 then
SetLength(PartitionenBaum,nextEmpty + PartitionenBaum[nextToDo].minHasseIdx + 2 + 1000);
nextEmptyBuf := nextEmpty;
for B:= PartitionenBaum[nextToDo].minHasseIdx downto 1 do
begin
PartitionenBaum[nextEmpty].minHasseIdx := B; PartitionenBaum[nextEmpty].faktor := HasseDiagramm[B].wert;
PartitionenBaum[nextEmpty].pred := nextToDo; PartitionenBaum[nextEmpty].wertHasseIdx := PartitionenBaum[nextToDo].wertHasseIdx;
for A:= 0 to High(HasseDiagramm[B].potenz) do
begin
if HasseDiagramm[B].potenz[A] > HasseDiagramm[ PartitionenBaum[nextToDo].wertHasseIdx ].potenz[A] then
begin
nextEmpty := nextEmpty - 1; Break; end;
PartitionenBaum[nextEmpty].wertHasseIdx := PartitionenBaum[nextEmpty].wertHasseIdx - potenzProd[A]*HasseDiagramm[B].potenz[A];
end;
nextEmpty := nextEmpty + 1;
end;
if (nextEmptyBuf = nextEmpty) then
if (PartitionenBaum[nextToDo].wertHasseIdx > 0) then
PartitionenBaum[nextToDo].pred := PRED_PRUNEDNODE - PartitionenBaum[nextToDo].pred else
leafCount := leafCount + 1; nextToDo := nextToDo + 1;
end;
SetLength(PartitionenBaum, nextEmpty);
time := GetTickCount - time;
Memo1.Lines.Add('--- Berechnung des Zerlegung-Baumes: '+inttostr(time)+'ms');
Memo1.Lines.Add(inttostr(leafCount)+' Zerlegungen ermittelt');
time := GetTickCount;
SetLength(bitmask, Length(PartitionenBaum));
for A:= 0 to High(PartitionenBaum) do
begin
bitmask[A] := true;
if PartitionenBaum[A].pred >= 0 then
bitmask[PartitionenBaum[A].pred] := false
else
begin
bitmask[A] := false;
if PartitionenBaum[A].pred <= PRED_PRUNEDNODE then
bitmask[PRED_PRUNEDNODE-PartitionenBaum[A].pred] := false
end;
end;
C := 0;
for A:= 0 to High(PartitionenBaum) do
if bitmask[A] = true then
begin
partitionCount := partitionCount + 1;
S := '';
pred := A;
while pred>-1 do
begin
if DOLOGGING then
S := S + inttostr(PartitionenBaum[pred].faktor)+'*';
pred := PartitionenBaum[pred].pred;
C := C+1;
end;
if DOLOGGING then
begin
S := Copy(S,1,Length(S)-3);
Memo1.Lines.Add('='+S);
end;
end;
time := GetTickCount - time;
Memo1.Visible := true;
Memo1.Lines.Add('--- Zerlegungen aufgezählt: ' + inttostr(partitionCount) + ' in ' + inttostr(C) + ' Iterationen' );
Memo1.Lines.Add('--- Zeitbedarf für Aufzählen: '+ inttostr(time)+'ms');
fullTime := GetTickCount - fullTime;
ShowMessage(inttostr(fullTime)+'ms');
end;
end. |
Edit:
Verbesserung möglich: Es ist garnicht nötig die Knoten im Hasse-Diagramm (und damit die Faktoren in der Zerlegung zu sortieren). Denn jede beliebige Reihenfolge ist eine ausreichende Sortierung. Es ist ja nur notwendig, dass nicht einmal 2*3*5 und ein anderes mal 5*2*3 bestimmt wird. Wenn ich definiere, die Reihenfolge ist [5,2,3], dann ist die Zerlegung in jedem Fall eindeutig.
Im Anhang jetzt noch das Delphi-Projekt. Seltsamerweise meckert mein Bug-verseuchtes Delphi 2005 plötzlich, er kann den Code nicht kompilieren und findet deshalb die "Project1.exe" nicht. Jeden Tag ein neuer Bug oder wie? :nixweiss:
Edit2:
Noch einen kleinen Bug gefixed (im Code oben und im Anhang). Leider weigert sich mein Delphi eine .exe zu erzeugen, wenn ich das Logging deaktiviere (auch nach PC-Neustart). Von daher konnte ich es nicht ordentlich testen.
Edit3:
Compilieren klappt, wenn ich die Überlaufprüfung und Bereichsprüfung ausschalte...
Horst_H - So 01.06.14 11:01
Hallo,
ich bin erlöst ;-)
Ich habe Dein Programm geändert. Lazarus konnte auch kompilieren, aber onFormShow brachte nichts.
Scheinbar waren die Memo noch nicht fertig.
Also ganz klassisch Button und für DoLogging ein Radiobutton.
Für die Hasse Knoten habe ich ein zweites Memo verwendet.Das war mir dann doch zu Quick und dirty.
Bei Speichern habe hin und herschieben habe ich es gelöscht...
Da wird sich auch
Mathematiker freuen,
Gruß Horst
Horst_H - So 01.06.14 16:07
Hallo,
ich habe es mal als Konsolenprogramm geschrieben, weil Lazarus mir einen Fehler meldete innerhalb seines intern genutzten AVL-Tree.
Edit: Neue Version, TreeNode Speicherbedarf gesenkt auf 12 Byte statt 24.
IntToStr eingespart durch einmaliges ausführen für jeden HasseKnoten.
Den Wert kann man über die Hasse-Knoten.Wert erhalten.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| Beispiel >>MaxLongInt,Cardinal 260e9
Voreingestellte Anzahl Knoten =4778596
(2,2,2,2,2,2,2 = 260620460100) 2*2 *3*3 *5*5 *7*7 *11*11 *13*13 *17*17
--- Zerlegungen aufgezaehlt: 4659138 in 28613155 Iterationen
--- Berechnung des Hasse-Diagramms : 1ms
--- Berechnung des Zerlegung-Baumes: 8527 ms
--- Zeitbedarf fuer Aufzaehlen : 304 ms
--- Zeitbedarf fuer Alles : 8839 ms
Speicherbedarf Knoten =379663500
Anzahl Knoten =31638625
Weiter mit <ENTER>-Taste |
Delphi-Quelltext
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:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
| program MulPart;
{$IFnDef FPC}
{$APPTYPE Console}
{$ELSE}
{$MODE Delphi}
{$OPTIMIZATION On}
{$OPTIMIZATION Peephole}
{$OPTIMIZATION CSE}
{$OPTIMIZATION ASMCSE}
{$ENDIF}
uses
SysUtils ;
const
PRED_ROOTNODE = -1;
PRED_PRUNEDNODE = -2;
type
THasseDiagrammKnoten = record
wert: Uint64;
potenz: array of integer;
end;
type TPartitionTreeNode = record
pred: integer;
minHasseIdx: integer;
wertHasseIdx: integer;
end;
var
HasseDiagramm: array of THasseDiagrammKnoten;
HasseSWert : array of String;
Primzahl: array of integer;
PartitionenBaum: array of TPartitionTreeNode;
function DeltaTime( dt:TDateTime): Cardinal;
const
cTimeToMs = 86400*1000;
begin
DeltaTime := round(dt*cTimeToMs);
end;
function IntPower(a,b : integer):Int64;
var
erg: Int64;
begin
IF b <0 then
erg := 0
else
begin
erg := 1;
repeat
iF b AND 1 = 1 then
erg := erg*a;
a:= a*a;
b := b shr 1;
until b = 0;
end;
IntPower:= erg;
end;
procedure Button1Click(DOLOGGING: boolean = true);var
partTime,
HasseTime,
SearchTime,
fullTime: TDateTime;
PrimCnt:integer;
A,B,C: integer;
S: String;
nextToDo: integer;
nextEmpty: integer;
nextEmptyBuf: integer;
leafCount: integer;
partitionCount: integer;
pred: integer;
potenzProd: array of integer;
bitmask: array of boolean;
begin
fullTime := time;
leafCount := 0;
partitionCount := 0;
SetLength( HasseDiagramm, 1 );
PrimCnt := 7;
SetLength( Primzahl, 12);
SetLength( HasseDiagramm[0].potenz, 12);
Primzahl[0] := 2;
HasseDiagramm[0].potenz[0] := 2;
Primzahl[1] := 3;
HasseDiagramm[0].potenz[1] := 2;
Primzahl[2] := 5;
HasseDiagramm[0].potenz[2] := 2;
Primzahl[3] := 7;
HasseDiagramm[0].potenz[3] := 2;
Primzahl[4] := 11;
HasseDiagramm[0].potenz[4] := 2;
Primzahl[5] := 13;
HasseDiagramm[0].potenz[5] := 2;
Primzahl[6] := 17;
HasseDiagramm[0].potenz[6] := 2;
Primzahl[7] := 19;
HasseDiagramm[0].potenz[7] := 1;
Primzahl[8] := 23;
HasseDiagramm[0].potenz[8] := 1;
Primzahl[9] := 29;
HasseDiagramm[0].potenz[9] := 1;
Primzahl[10] := 31;
HasseDiagramm[0].potenz[10] := 1;
Primzahl[11] := 37;
HasseDiagramm[0].potenz[11] := 1;
HasseDiagramm[0].wert := 1;
B := 1;
With HasseDiagramm[0] do
begin
for A:= PrimCnt-1 downto 0 do
B := B* IntPower(primzahl[A],potenz[A]);
end;
HasseDiagramm[0].wert := B;
writeln('--- Eingabezahl: ' + inttostr(B) );
SetLength(potenzProd, PrimCnt);
C := 1;
for A:= 0 to PrimCnt-1 do
begin
potenzProd[A] := C;
C := C*(HasseDiagramm[0].potenz[A]+1);
end;
writeln('--- Knoten im Hassediagramm: ' + inttostr(C) );
parttime := time;
SetLength(HasseDiagramm,C);
SetLength(HasseSWert,C);
for A:= High(HasseDiagramm) downto 0 do
begin
C := A;
SetLength(HasseDiagramm[A].potenz, PrimCnt);
With HasseDiagramm[A] do
begin
Wert := 1;
for B:= PrimCnt-1 downto 0 do
begin
potenz[B] := C div potenzProd[B];
C := C mod potenzProd[B];
Wert := Wert * IntPower(Primzahl[B],potenz[B]);
end;
HasseSWert[A] := IntToStr(Wert)+'*';
end;
end;
HasseTime := time-parttime;
if DOLOGGING then
for A:= 0 to High(HasseDiagramm) do
begin
S := '(';
for B:= 0 to PrimCnt-1 do
S := S + inttostr(HasseDiagramm[A].potenz[B])+',';
setlength(S,Length(S)-1);
S:= S + ' = '+inttostr(HasseDiagramm[A].wert)+')';
writeln(S);
end;
SetLength(PartitionenBaum,sqr(High(HasseDiagramm)));
writeln('Voreingestellte Anzahl Knoten =',Length(PartitionenBaum));
Searchtime := time;
PartitionenBaum[0].minHasseIdx := High(HasseDiagramm); PartitionenBaum[0].pred := PRED_ROOTNODE; PartitionenBaum[0].wertHasseIdx := High(HasseDiagramm);
nextToDo := 0;
nextEmpty := 1;
while nextToDo < nextEmpty do
begin
if High(PartitionenBaum) < nextEmpty + PartitionenBaum[nextToDo].minHasseIdx + 1 then
SetLength(PartitionenBaum,nextEmpty + PartitionenBaum[nextToDo].minHasseIdx + sqr(High(HasseDiagramm)));
nextEmptyBuf := nextEmpty;
for B:= PartitionenBaum[nextToDo].minHasseIdx downto 1 do
begin
with PartitionenBaum[nextEmpty] do
begin
minHasseIdx := B; pred := nextToDo; wertHasseIdx := PartitionenBaum[nextToDo].wertHasseIdx;
end;
for A:= 0 to High(HasseDiagramm[B].potenz) do
begin
if HasseDiagramm[B].potenz[A] > HasseDiagramm[ PartitionenBaum[nextToDo].wertHasseIdx ].potenz[A] then
begin
nextEmpty := nextEmpty - 1; Break; end;
DEC(PartitionenBaum[nextEmpty].wertHasseIdx,potenzProd[A]*HasseDiagramm[B].potenz[A]);
end;
nextEmpty := nextEmpty + 1;
end;
if (nextEmptyBuf = nextEmpty) then
if (PartitionenBaum[nextToDo].wertHasseIdx > 0) then
PartitionenBaum[nextToDo].pred := PRED_PRUNEDNODE - PartitionenBaum[nextToDo].pred else
leafCount := leafCount + 1; nextToDo := nextToDo + 1;
end;
SearchTime := time-partTime;
SetLength(PartitionenBaum, nextEmpty);
partTime := Time;
SetLength(bitmask, Length(PartitionenBaum));
for A:= 0 to High(PartitionenBaum) do
begin
bitmask[A] := true;
if PartitionenBaum[A].pred >= 0 then
bitmask[PartitionenBaum[A].pred] := false
else
begin
bitmask[A] := false;
if PartitionenBaum[A].pred <= PRED_PRUNEDNODE then
bitmask[PRED_PRUNEDNODE-PartitionenBaum[A].pred] := false
end;
end;
s :='=';
C := 0;
IF leafCount > 25000 then
doLogging := false;
for A:= 0 to High(PartitionenBaum) do
if bitmask[A] = true then
begin
partitionCount := partitionCount + 1;
pred := A;
while pred>0 do
begin
if DOLOGGING then
S := S + HasseSWert[PartitionenBaum[pred].minHasseIdx];
pred := PartitionenBaum[pred].pred;
C := C+1;
end;
if DOLOGGING then
begin
setlength(S,Length(S)-1);
writeln(S);
s :='=';
end;
end;
partTime := time-partTime;
fullTime := time - fullTime;
writeln(HasseSWert[High(HasseSWert)]);
writeln(inttostr(leafCount)+' Zerlegungen ermittelt');
writeln('--- Zerlegungen aufgezaehlt: ' + inttostr(partitionCount) + ' in ' + inttostr(C) + ' Iterationen' );
writeln('--- Berechnung des Hasse-Diagramms : ',DeltaTime(Hassetime),'ms');
writeln('--- Berechnung des Zerlegung-Baumes: ',DeltaTime(SearchTime),' ms');
writeln('--- Zeitbedarf fuer Aufzaehlen : ',Deltatime(parttime),' ms');
writeln('--- Zeitbedarf fuer Alles : ',Deltatime(fulltime),' ms');
writeln('Speicherbedarf Knoten =',Length(PartitionenBaum)*SizeOF(TPartitionTreeNode));
writeln('Anzahl Knoten =',Length(bitmask));
Writeln('Weiter mit <ENTER>-Taste');
READln;
end;
begin
Button1Click;
end. |
Gruß Horst
Xion - So 01.06.14 18:31
Was den Speicherbedarf angeht, lasse dir mal Length(PartitionenBaum) ausgeben. Das record pro Element sind immerhin 6*32bit, da kommt schon etwas an Speicherbedarf zusammen. (Abhängig von der Anzahl Zerlegungen!)
Dann fällt mir auf, dass du das record als "packet record" definiert hast, was durchaus Zeit kosten kann, weil diese Records den Kern des Algorithmus ausmachen.
Und dann kannst du noch das Array anders/schneller vergrößern. Ersetze z.B. einfach mal in Zeile 180 die 1000 durch 1000000. Vielleicht ist Lazarus nicht so gut im realloiziieren ;)
Horst_H - So 01.06.14 19:03
Hallo,
ich bin entsetzt, moralisch enttäuscht!
Mit dem passenden setlength in Zeile 180 sind es nur noch 931 ms .
Wahrscheinlich war die Speicherverwaltung von Lazarus mittels AVL-Tree an Ihre Grenzen gekommen.
packed kompacktiert nur innerhalb des records ( wäre bei allen Daten n*32 Bit aber egal gewesen ).Array wird soweit ich weiß lückenlos angelegt.
Dann kann ich ja nochmal Motorradfahren :-)
Gruß Horst
Edit:
Neue Version oben.
Treenode braucht nur noch die Hälfte an Platz.
Das Beispiel 2⁴*3⁴*5⁴*7⁴ dauert jetzt etwa 620 ms.
Horst_H - Mi 04.06.14 21:52
Hallo,
etwas erstaunliches ist mir gerade aufgefallen.
Wenn man nur Potenzen von 1 bei den Primzahlen hat ( 2*3*5*7*11 ...)
Dann ist die Anzahl der Knoten( n Primzahlen ) = Anzahl der Zerlegungen (n+1-Primzahlen)
Quelltext
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:
| Anzahl Primfaktoren 1 =2
--- Zerlegungen aufgezaehlt: 1 in 1 Iterationen
--- Zeitbedarf fuer Alles : 7 ms
Anzahl Knoten =2
Anzahl Primfaktoren 2 =2*3
--- Zerlegungen aufgezaehlt: 2 in 3 Iterationen
--- Zeitbedarf fuer Alles : 7 ms
Anzahl Knoten =5
Anzahl Primfaktoren 3 =2*3*5
--- Zerlegungen aufgezaehlt: 5 in 10 Iterationen
--- Zeitbedarf fuer Alles : 7 ms
Anzahl Knoten =15
Anzahl Primfaktoren 4 =2*3*5*7
--- Zerlegungen aufgezaehlt: 15 in 37 Iterationen
--- Zeitbedarf fuer Alles : 7 ms
Anzahl Knoten =52
Anzahl Primfaktoren 5 =2*3*5*7*11
--- Zerlegungen aufgezaehlt: 52 in 151 Iterationen
--- Zeitbedarf fuer Alles : 6 ms
Anzahl Knoten =203
Anzahl Primfaktoren 6 =2*3*5*7*11*13
--- Zerlegungen aufgezaehlt: 203 in 674 Iterationen
--- Zeitbedarf fuer Alles : 5 ms
Anzahl Knoten =877
Anzahl Primfaktoren 7 =2*3*5*7*11*13*17
--- Zerlegungen aufgezaehlt: 877 in 3263 Iterationen
--- Zeitbedarf fuer Alles : 6 ms
Anzahl Knoten =4140
Anzahl Primfaktoren 8 =2*3*5*7*11*13*17*19
--- Zerlegungen aufgezaehlt: 4140 in 17007 Iterationen
--- Zeitbedarf fuer Alles : 9 ms
Anzahl Knoten =21147
Anzahl Primfaktoren 9 =2*3*5*7*11*13*17*19*23
--- Zerlegungen aufgezaehlt: 21147 in 94828 Iterationen
--- Zeitbedarf fuer Alles : 32 ms
Anzahl Knoten =115975
Anzahl Primfaktoren 10 =2*3*5*7*11*13*17*19*23*29
--- Zerlegungen aufgezaehlt: 115975 in 562595 Iterationen
--- Zeitbedarf fuer Alles : 212 ms
Anzahl Knoten =678570
Anzahl Primfaktoren 11 =2*3*5*7*11*13*17*19*23*29*31
--- Zerlegungen aufgezaehlt: 678570 in 3535027 Iterationen
--- Zeitbedarf fuer Alles : 1742 ms
Anzahl Knoten =4213597
Anzahl Primfaktoren 12 =2*3*5*7*11*13*17*19*23*29*31*37
--- Zerlegungen aufgezaehlt: 4213597 in 23430840 Iterationen
--- Zeitbedarf fuer Alles : 15394 ms
Anzahl Knoten =27644437 |
Ich suchte nach einer Formel für die passende Vorab-Speicherbelegung, weil die bei mir so langsam ist.
Nebenbei wurde es etwas schneller, aber undurchschaubarer.
Gruß Horst
Horst_H - Do 05.06.14 19:03
Hallo,
ich habe Turbo-Delphi bemüht und es hat sich bequemt.
Die Umstellung aus Lazarus, war nicht aufwendig, weil es auch nichts spezielles beinhaltet.
Ich habe dort die Ausgabe auf 22000 Zeilen begrenzt, das dauert ja ewig. ( linux/wine )
Die Ausgabe habe ich aber dennoch in eine Stringliste gepackt, damit man sieht, dass dies recht flott ist.
Was fehlt ist die Eingabe einer Zahl und deren Aufteilung in Primfaktoren und deren Potenzen, aber das ist ja eine leichte Übung, für Zahlen < MaxLongInt für den Bereich darüber gibt es sicher auch etwas.
Dank
Xion saust es nur so dahin.
Gruß Horst
P.S
Video geändert
http://www.youtube.com/watch?v=nD8ErWgj5Ac Hassediagramme (Teil 1) von Prof. Christian Spannagel an der PH Heidelberg
Irgendwas läuft noch grundlegend falsch :-(
Ich will nicht so viele unnötige Knoten anlegen lassen.
Man muss ja bei der Teilbarkeit immer abwärts gehen.Wie man aber an der Ausgabe sieht, wird das nicht eingehalten:
Produkt der ersten 9 Primzahlen
2*3*5..*19*.23 :[ meine Güte 34 Sekunden unter linux/wine für die Ausgabe ins Memo... ]
....
=746130*299
=4199*53130
=8398*26565
=12597*17710
=25194*8855
=20995*10626
=41990*5313
=62985*3542
=125970*1771
...
Irgendwo , muss man noch einbauen, das der vorherige Faktor > war. Die Jetzige Positoin ist scheinbar nicht optimal.
Vielleicht müsste ein Zähler an jeden Teiler, wie oft er benutzt wurde.Möglicherweise gibt es da eine Rechnenvorschrift, diese Anzahl vorab zu bestimmen.
Mathematiker - So 08.06.14 21:56
Hallo,
ich bin wieder "online" und habe angefangen, Eure vielen Beiträge zu verstehen.
Und wie oft verstehe ich erst einmal wieder sehr wenig. Aber ich kämpfe mich durch.
Erst einmal Danke an
Horst_H und
Xion.
Beste Grüße
Mathematiker
Horst_H - Di 17.06.14 22:22
Hallo,
ich grübele immer noch über eine Vereinfachung nach, ohne dieses Knotenungetüm aufbauen zu müssen.
Es ist ja ein leichtes alle Teiler zu ermitteln, wenn man die Primfaktorzerlegung hat, noch schneller.
Was ich suche, ist eine Abbruchbedingung, das ich nicht doppelte Produkte erzeuge.
Dazu mal dieser Ansatz:
Ich spalte einen kleiner oder gleichen Faktor ab und zerlege dann nur noch vorderen größeren.
//Schönerweise sind die Teiler der Teiler ebenso darin enthalten und
//man kann die Position in der Teilerliste aus den Potenzen berechnen
//weshalb man die Teilerliste nicht einfach sortieren kann.
//
Xion berechnet so auch die Knotenpositionen.
Als Beispiel 36 = 3^2 x 2^2.
Quelltext
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:
| Prim-Potenz
Prim-> 3 2
Zahl
36 2 2
18 2 1
9 2 0
12 1 2
6 1 1
3 1 0
4 0 2
2 0 1
1 0 0
Aufteilen der 36 in Faktoren:
36 = 36x1
jetzt 36 aufteilen
36 = 18 x 2 -> eine Lösung
jetzt 18 aufteilen
9x2 x2 -> eine Lösung
jetzt 9 aufteilen
3x3 x2x2 -> eine Lösung
nächste von 18 ist 6
6 x3 x2 -> eine Lösung
jetzt 6 aufteilen
3 x2 x3 x2
der kleinere Faktor vorne ist kleiner als der zuvor,
also geht es nicht.Kommt auch schon
bei der Aufteilung der 9 vor
18 ist jetzt abgeschlossen, jetzt käme als nächstes in der Liste 9
36 = 9 x 4 -> eine Lösung
jetzt 9 aufteilen
3x3 x4 ; 3 < 4 also hier keine Lösung
9 ist jetzt abgeschlossen, jetzt käme als nächstes in der Liste 12
36 = 12 x 3 -> eine Lösung
jetzt 12 aufteilen
4x3 x 3 das geht, -> eine Lösung, bei 9 zuvor nicht
jetzt 4 aufteilen
2x2 x3x3 2<3 also keine Lösung
12 ist jetzt abgeschlossen, jetzt käme als nächstes in der Liste 6
36 = 6 x 6 -> eine Lösung
jetzt vordere 6 aufteilen
3x2 x6 Faktoren kleiner als Faktor folgend, also keine Lösung.
Die folgenden Teiler von 36 < sqrt(36) -> habe fertig
Lösungen:
36 x1
18 x 2
9 x 2 x 2
3x3 x 2 x 2
6x3 x 2
9 x 4
12 x 3
4x3 x 3
6 x 6 |
das passt zu den Lösungen per Hassediagramm:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| )
=36
=2*18
=4*9
=3*12
=6*6
=2*2*9
=2*3*6
=4*3*3
=2*2*3*3 |
Jetzt sollte ich das mal im Programm umsetzen.Ich weiß nicht, ob die Bedingung hinwendig oder nur notreichend ist ;-)
Gruß Horst
EDIT:
Funktinioniert nicht :-(
16 = 2^4, dann erzeuge ich immer alles nochmals, weil die Abbruchbedingung nie greifen kann.
Horst_H - Mi 18.06.14 15:02
Hallo,
ein neuer Ansatz, der zu banal ist.
Man fügt einfach( multipliziert ) immer eine Primzahl zu allen Faktoren hinzu, insbesondere die 1
2*3*5*7 = 210 hat nur Primzahlen in der Potenz 1.
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
| erst
2x1
jetzt 3 hinzu, dazu jeden Faktor des vorangegangen Produktes multiplizieren
ergibt
(3x2)x1 sowie
2x(3x1)
1x6,2x3 = 2 Aufteilungen
die 5
1x6 -> 5x6 und 1x30
1x2x3 -> 5x2x3 ,1x10x3 und 1x2x15
1x30
15x2
10x3
6x5
5x3x2x1 = 5 Aufteilungen
die 7
30x1 -> 7x30, 1x210
15x2x1 -> 105x2, 15x14,15x2
10x3x1-> 70x2, 10x21,10x3x7
6x5x1 -> 42x5, 6x35,6x5x7
5x3x2x1->35x3x2,5x21x2,5x3x14 und 5x3x2x7 = 15 Aufteilungen |
Erschreckend simpel ;-)
Gruß Horst
Horst_H - Fr 20.06.14 18:54
Gelöscht
Edit:
Der Gedanke, es würden unnötig viele Knoten erzeugt, ist falsch.
Wenn 2^60 ~ 900000 Partitionen vorhanden sind bestehen diese ja aus unterschiedlicher Anzahl an Faktoren. Diese sind ja in den Knoten gespeichert.
6 Mio Knoten ist ja dann nicht so viel, es gibt doch von 1 bis 60 Faktoren einer Partition.
Irgendwie hänge ich an dem Gedanken fest, das von unten nach oben aufzubauen, eben Faktor für Faktor hinzuzufügen.
36 wäre dann 2-> 2 ,2->2,2,3 -> 2,2,3,3
Gruß Horst
Xion hätte bessere Namen wählen sollen:
Statt:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| type TPartitionTreeNode = record
pred: integer;
faktor: int64;
minHasseIdx: integer;
wertHasseIdx: integer;
end; |
lieber:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
| type TPartitionTreeNode = record
pred: integer; faktor: int64;
KnNrDivisor : integer; KnNrQuotient:integer; end; |
Dann erkennt man auch viel leichter, das man enorm viel einsparen kann.
Wenn ich 2^4x3^4 habe kommt sicher sehr oft 2^2x3^2 auf dem Weg der Teibarkeit vor( etwa .2^(4-2)x3^(4-2) = 36 mal ).
Wenn ich einmal die Aufteilung von 2^2x3^2 habe, dann sollte das wohl reichen.
Aber wie geht man dann richtig vor?
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!