Zahl in Summanden zerlegen

[DeerHunter]

Hallo.

Folgendes Problem: ich habe eine Zahl X (ganzzahlig) die aus n verschiedenen, ebenfalls ganzzahligen Summanden bestehen soll. Die Summanden sollen alle größer 0 sein und dürfen wie gesagt nicht doppelt vorkommen. Ich möchte nun ein Programm schreiben, das mir alle hierbei möglichen Kombinationen ausgibt, wenn ich die Zahl und die Anzahl der Summanden angebe.

Meine bisherige Lösung sah so aus, dass ich für die Summanden ein dynamisches Array aus Integern angelegt habe, per Schleife dann die Summanden jeweils immer um 1 erhöht bis ich für alle mal alle Werte von 1..X durchhatte und dann einfach bei jedem Schleifendurchgang geprüft, ob sich a) die Summanden alle unterscheiden und b) ob sie addiert meine Zahl X ergeben. Wenn das der Fall ist wird die Konstellation eben als Möglichkeit ausgegeben.
Natürlich ist das alles andere als effizient und bei größeren Zahlen und/oder vielen Summanden kommt man so leider auch nicht in akzeptabler Rechenzeit zu einem Ergebnis......(immerhin sind das so X^n Schleifendurchläufe... und die Vergleiche ob sich alle Summanden unterscheiden sind auch nochmal nicht wenig)
Desweiteren gibt es hier noch das Problem, dass eine Lösung durchaus mehrmals aufgelistet wird, nur halt in anderer Reihenfolge der Summanden, was ich aber auch garnicht will.

Meine Frage also: gibt es eine Möglichkeit das Problem auf elegantere Weise zu lösen, sodass man vielleicht sogar auch bei größeren Zahlen/vielen Summanden zu einem Ergebnis kommen kann? Wenn ja, wie stell ich das so genau an?

[fiasko]

Man kann das noch ein bißchen optimieren. Idee:

Code:

z=20    ; Zahl X
n= 5    ; Summanden 

k=1  k=2  k=3  k=4  k=5
16
14
13
12
11
10
 9
 8    9
 7    7
 6    6    7
 5    5    5    6
 4    4    4    4    5
 3    3    3    3    3
 2    2    2    2    2
 1    1    1    1    1

höchster Wert einer Spalte:
 (z-(n-k+1))/k+1

Das sollten alle möglichen Kombinationen von Summanden enthalten. Wenn man nun die Zahl aufbaut einfach von der rechten Spalte an immer eine Zahl nehmen, dann eine Spalte nach links und eine Zahl die größer-gleich der letzten ist nehmen. Damit dürften auch keine Dopplungen mehr auftreten.

Delphi-Quellcode:

uses sysutils;              

{
  n: Anzahl Summanden
  k: aktueller Summand (start bei k=n)
  z: Zahl X
  s: aktuelle Summe
  l: letzter Summand (start bei 1)
  str: aktuelle Zahl
}

procedure zahl(n,k,z,s,l: Integer; str: String);
var
  i: Integer;
begin
  if k=0 then
  begin
    if(s=z) then
      writeln(str);
    exit;
  end;                                                                                                                                                           

  for i:=l to ((z-(n-k+1)) div k)+1 do
    zahl(n,k-1,z,s+i,i,str+inttostr(i)+' ');
end;

begin
  { Zahl 20 in 5 Faktoren zerlegen }
  zahl(5,5,20,0,1,'');
end.

(kA ob da alle Lösungen rauskommen... müßte man mal überprüfen )

[ibp]

@ fiasko glaube nicht das mit deinem algorythmus alle kombinationen herauskommen
... versuch es mal damit
z=8, n=3

Code:

1 2 3 
1 3 4 
1 4 5 
1 5 6 
1 6 7 
1 7 8
1 8
2 3 4
2 4 5
2 5 6
2 6 7
2 7 8
2 8
...
8

1. dazu brauchst du ein array der größe [(z-1)!,n].
2. das sollte sich mit dynamischen arrays lösen lassen.
3. durchlaufe das array und lösche alle felder die nicht summe(array[i,1..n])=z sind!
4. alles was übrig bleibt sollten alle kombinationen sein...
gruß rené

ps übrigens kannst du die anzahl der möglichen kombinationen berechnen der begriff (n über k) hilft dir weiter

[fiasko]

Zitat von ibp:

@ fiasko glaube nicht das mit deinem algorythmus alle kombinationen herauskommen
... versuch es mal damit
z=8, n=3

Das wäre dann:
zahl(3,3,8,0,1,'');

Code:

1tl1@home2:~/tmp$ ./test
1 1 6
1 2 5
1 3 4
2 2 4
2 3 3

das sind doch alle Lösungen???

Zitat von ibp:

1. dazu brauchst du ein array der größe [(z-1)!,n].
2. das sollte sich mit dynamischen arrays lösen lassen.
3. durchlaufe das array und lösche alle felder die nicht summe(array[i,1..n])=z sind!
4. alles was übrig bleibt sollten alle kombinationen sein...

das ist aber reichlich uneffektiv. Mußt ja erstmal das Array aufbauen... außerdem braucht sich mein Algorithmus keine Gedanken um die Reihenfolge zu machen.

[edit]
Gerade aufgefallen:

Zitat von ibp:

1. dazu brauchst du ein array der größe [(z-1)!,n].

Das sind für z.B. z=20: 2432902008176640000*n Felder, mit Int und n=5 also 48658040163532800000, d.h. ~44254229 TERRABYTEs!
[/edit]

[ibp]

... das stimmt schon ist nicht sonderlich effektiv, deswegen ja dynamische arrays, für alle wege die ins nichts führen kann man das dann sofort dekrementieren.
... sollte ja auch nur ein denkanstoß sein ist aber zum überfluß noch ein fehler drin...
... deins könnte man aber noch in der hinsicht optimieren, daß es nicht bei 1 1 1 1 anfängt, da die summanden sich ja nicht wiederholen sollen !

[fiasko]

Zitat von ibp:

... deins könnte man aber noch in der hinsicht optimieren, daß es nicht bei 1 1 1 1 anfängt, da die summanden sich ja nicht wiederholen sollen

das kann man eigentlich nur bei der letzten Spalte (also der Ersten) optimieren: testen ob i>z-s wenn k=1 ist... dürfte aber nicht viel bringen da der nächste Aufruf von zahl eh abbricht.

Das mit dem wiederholen habe ich so verstanden das die Reihenfolge der Zahlen egal ist, also 1 1 1 16 und 1 1 16 1 zusammengefaßt werden sollen .

[ibp]

ja schon, aber wenn mann bei 1,2,3,4.. beginnen würde, könnte man sich die ersten abbrüche/zusammenfassungen sparen.

[DeerHunter]

Ah, danke fiasko, das funktioniert
nur können bei deiner Lösung so noch Summanden doppelt vorkommen, aber das bekomm ich schon hin denk ich

[fiasko]

Achso, ja, wer lesen kann ist klar im Vorteil ...


Das ist aber auch ganz einfach, man ersetzt die for-Schleife durch:

Delphi-Quellcode:

  for i:=l to ((z-n+k) div k)+1 do
    zahl(n,k-1,z,s+i,i+1,str+inttostr(i)+' ');

und das sollte es sein.