Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Algorithmus zum Ausgeben aller Kombinationen


mr.goalie - Sa 07.10.06 15:08
Titel: Algorithmus zum Ausgeben aller Kombinationen
Hey Leute!

Ich hab ein riesiges Problem: Ich brauche einen Algorithmus (z.B. in Form einer Procedur oder so) mit dem ich alle Kombinationen eines Arrays ausgeben kann. Dabei sind einzugeben: k und n --> also alles was man für die kombinationen benötigt.

Ich hab echt keine Idee dafür und hoffe, dass ein paar von den erfahrenen Programmierern den Algo vll schon kennen oder mir sonst irgendwie helfen können.
Die Suchfunktion hab ich schon genutzt, aber nichts gefunden :(

Danke schonmal im vorraus für jede Hilfe!!!


Kroko - Sa 07.10.06 15:13

Wie würdest Du es denn "per Hand" machen?
Die ersten k aus n nehmen und dann das letzte ändern bis es nicht mehr geht, dann das vorletzte ändern, und wieder das letzte bis es nicht mehr geht usw usf. Nun setzte das um, stelle Quellen hier ein, wenn es nicht weiter geht.
Deine HA wird hier niemand machen!


mtin - Sa 07.10.06 15:28

hab hier was gefunden, was alle zusammenstellungen von 3 aus 10 Ziffern findet, aber wie man das nun ganz allgemein für beliebige n's und k's hinbekommt fällt mir jetzt auch nicht sofort ein...


Delphi-Quelltext
1:
2:
3:
4:
for i := 0 to 7 do 
  for j := i+1 to 8 do 
    for k := j+1 to 9 do 
      CombiList.Add(IntToStr(i) + '/' + IntToStr(j) + '/' + IntToStr(k) );


Gravitar - Sa 07.10.06 20:59
Titel: Re: Algorithmus zum Ausgeben aller Kombinationen
Hi,

das hört sich ziemlich stark nach Permutation an.

Einfach hier im Forum nach diesem Begriff suchen, dort findest Du diverse Quellen

Gruß, Andreas


alzaimar - Sa 07.10.06 21:53

Hier http://www.delphipraxis.net/topic93812,15.html wurde vor Kurzem das Problem diskutiert.


mr.goalie - So 08.10.06 10:43

Danke für die Antworten, aber ich suche wirklich nach einem Algo für Kombinationen (da is noch ein kleiner Unterscheid zu Permutationen)
Definition: Kombinationen sind k-elemtige Auswahlen aus einer n-elementigen Menge ohne Berücksichtigung der Reihenfolge. :mahn:

Der Hinweis von mtin war gut. Ich habe einmal versucht dies zu verallgemeinern (mit Rekursion), aber irgendwie funktioniert es noch nicht. :(
Kann mir einer sagen, was daran falsch ist?


Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure kombinationen(stufe:Integer;n:Integer;k:Integer);
var j,i:Integer;
begin
  for j := feld[stufe-1] to (n-k+stufe) do
    begin

      feld[stufe]:=j;
      if stufe < k-1 then
      kombinationen(n,k,stufe+1)
      else
      begin
        for i:=0 to k - 1 do
        Form1.Memo1.Lines.Add(IntToStr(feld[i]) + '/');
      end;
    end;
end;


@Kroko:Tschuldigung, wenn das falsch rüber gekommen ist, aber ich meinte natürlich nicht, dass ihr mir den Algo schreiben solltet. Es hätte ja einfach sein können, dass sich schonmal jemand damit beschäftigt hat (und man muss das Rad ja nicht zweimal erfinden ^^)
Ich wollte wirklich eher Anregungen und die von mtin wahr verdammt gut! (nochmals thx)


alzaimar - So 08.10.06 11:06

Sag das doch gleich. So vielleicht?

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
Procedure TForm1.Kombination (Const aString, aResult: String; anIndex, aMax: Integer;
  aUsedChars: TCharSet);
Var
  i: Integer;

Begin
  For i := 1 To Length(aString) Do
    If Not (aString[i] In aUsedChars) Then
      If anIndex = aMax Then
        Memo1.lines.add(aResult + aString[i])
      Else
        Kombination (aString, aResult + aString[i], anIndex + 1, aMax, aUsedChars +
          [aString[i]]);
End;

Procedure TForm1.Button1Click(Sender: TObject);
Begin
  Kombination (edit1.text,'',1,3,[]); // <--- k = 3
End;


Reinhard Kern - So 08.10.06 11:24
Titel: Re: Algorithmus zum Ausgeben aller Kombinationen
user profile iconmr.goalie hat folgendes geschrieben:
Hey Leute!

Ich hab ein riesiges Problem: Ich brauche einen Algorithmus (z.B. in Form einer Procedur oder so) mit dem ich alle Kombinationen eines Arrays ausgeben kann. Dabei sind einzugeben: k und n --> also alles was man für die kombinationen benötigt.

Ich hab echt keine Idee dafür und hoffe, dass ein paar von den erfahrenen Programmierern den Algo vll schon kennen oder mir sonst irgendwie helfen können.
Die Suchfunktion hab ich schon genutzt, aber nichts gefunden :(

Danke schonmal im vorraus für jede Hilfe!!!


Hallo,

da ich nicht wirklich verstehe, was du fragen willst, rate ich mal: du hast ein 2dimensionales Array der Gröss k x n und möchtest auf jedes einzelne Datum im Array zugreifen. Dafür gibt es die FOR-Schleifen:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
procedure TuWasAlle (k,n : integer);
var i,j : integer;
begin
for i := 1 to k do
  for j := 1 to n do
    TuWasEinzeln (array[i,j]);
end;


Wenn dein array nicht mit 1 startet, must du das natürlich anpassen.

Gruss Reinhard


mr.goalie - So 08.10.06 11:47

user profile iconReinhard Kern hat folgendes geschrieben:

da ich nicht wirklich verstehe, was du fragen willst, rate ich mal: du hast ein 2dimensionales Array der Gröss k x n und möchtest auf jedes einzelne Datum im Array zugreifen. Dafür gibt es die FOR-Schleifen:


hm, so einfach ist es nicht. Wie du schon bei mtins Programmauszug gesehen hast ist die Anzahl der der FOR-Schleifen wichtig, da diese nämlich k ist.

Das Programm soll einfach nur alle Kombinationen mit variablen n und k ausgeben, z.B.
n =4, k=2:
1/2
1/3
1/4
2/3
2/4
3/4

@alzaimar:Deins sieht ziemlich komplex und ehrlich gesagt blicke ich da nicht hundertprozentig durch :(
trotzdem danke, ich versuche es weiter!


Delete - So 08.10.06 15:10

sowas vielleicht:

http://www.delphi-forum.de/viewtopic.php?t=64053&highlight=permutation
http://www.delphi-forum.de/viewtopic.php?t=39840&highlight=permutation


Horst_H - So 08.10.06 15:35

Hallo,,
so etwa in Rekursiv?
2 Edits ein Button ein Memo


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:
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

function NUeberK(n,k:integer):int64;
var
  i : integer;
begin
//Kein Test auf negative Zahlen oder andere Hinterhaeltigkeiten)
  result := 1;
  i := 1;
  while i<=K do
    begin
    result := result*n div I;// Teilt IMMER ohne Rest!
    inc(i);
    dec(n);
    end;

end;
procedure NUeberKKomb(var outString:String;RestString:string;k:integer);
var
  I,l : Integer;
  chTmp : Char;
  Rs:string;
begin
  If K<1 then
    exit;
  For i := length(RestString) downto 1 do
    begin
    //Anhaengen
    outString := outString+RestString[i];
    l := length(RestString);
    //entfernen durch Austausch mit letztem
    Reststring[i] := Reststring[l];
    // und string um eins kuerzen
    setlength(Reststring,l-1);
    (* Form1.Memo1.lines.Add(Format('%d %d %s:%s',[l,i,outString,Reststring]));*)

    //Falls k-Reihe noch nicht fertig
    IF k>1 then
      NUeberKKomb(outString,Reststring,k-1)
    else
      //Ausgabe und kuerzen um eine Position
      begin
      Form1.Memo1.lines.Add(outString);
      setlength(outString,length(outString)-1);
      end;
   end;
   setlength(outString,length(outString)-1);
end;

procedure TForm1.Button1Click(Sender: TObject);
var

  Test,StartString :string;
  n,k,i : integer;
begin
  Test := '';
  n := StrToInt(Edit1.Text);
  k := StrToInt(Edit2.Text);
  form1.Memo1.Lines.Clear;
  form1.Memo1.Lines.Add(Format('Es sind %d Möglichkeiten',[NUeberK(n,k)]));
  For i := 1 to n do
    StartString := StartString+chr(i+ord('A')-1);
  NUeberKKomb(Test,StartString,k);
end;

end.


Bitte nicht 26 26 testen, da klemmt es
Gruss Horst


mr.goalie - So 08.10.06 15:55

cool, ich muss mich noch reindenken, aber das sieht erstma klasse aus und funktioniert auch.
DANKE!!!


alzaimar - So 08.10.06 17:36

user profile iconmr.goalie hat folgendes geschrieben:
@alzaimar:Deins sieht ziemlich komplex und ehrlich gesagt blicke ich da nicht hundertprozentig durch :(
trotzdem danke, ich versuche es weiter!

:shock: 6 Zeilen sind komplex? Rufe doch meine Routine einfach mal auf und steppe Zeile für Zeile durch den Code. Lasse dir die Parameter per 'watch' anzeigen.

Delphi-Quelltext
1:
Kombination ('1234','',1,2,[]); // <--- n=4, k=2                    

Im Prinzip ist das doch das Gleiche wie bei Horst_H.