| Autor |
Beitrag |
Mathematiker
  
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mi 28.05.14 08:28
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 de.wikipedia.org/wik...iplikative_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. 
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Horst_H
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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 www.entwickler-ecke....=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
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: 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.
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. _________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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.
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.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker 
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mi 28.05.14 22:12
Hallo,
So selbstbezogen, wie ich bin:
www.entwickler-ecke....der=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
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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 _________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Zuletzt bearbeitet von Hidden am Mi 28.05.14 23:36, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: 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 
.. 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 \{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 
beste Grüße zurück,
Daniel _________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
Zuletzt bearbeitet von Hidden am Do 29.05.14 14:57, insgesamt 1-mal bearbeitet
|
|
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: Do 29.05.14 01:05
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: 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
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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 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
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: 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 
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  _________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|
