Autor Beitrag
mr.goalie
Hält's aus hier
Beiträge: 10



BeitragVerfasst: Sa 07.10.06 15:08 
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 1284

W98 W2k WXP
Turbo D
BeitragVerfasst: 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!

_________________
Die F1-Taste steht nicht unter Naturschutz und darf somit regelmäßig und oft benutzt werden! oder Wer lesen kann, ist klar im Vorteil!
mtin
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 177

Win XP SP2
BDS2006 Enterprise
BeitragVerfasst: 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...

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 41

Win XP
D6 Ent
BeitragVerfasst: Sa 07.10.06 20:59 
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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Sa 07.10.06 21:53 
Hier www.delphipraxis.net/topic93812,15.html wurde vor Kurzem das Problem diskutiert.

_________________
Na denn, dann. Bis dann, denn.
mr.goalie Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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?

ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: So 08.10.06 11:06 
Sag das doch gleich. So vielleicht?
ausblenden 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;

_________________
Na denn, dann. Bis dann, denn.
Reinhard Kern
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 591
Erhaltene Danke: 14



BeitragVerfasst: So 08.10.06 11:24 
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:

ausblenden 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 Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: 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!
Grenzgaenger
Ehemaliges Mitglied
Erhaltene Danke: 1



BeitragVerfasst: So 08.10.06 15:10 
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: So 08.10.06 15:35 
Hallo,,
so etwa in Rekursiv?
2 Edits ein Button ein Memo

ausblenden volle Höhe 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 Threadstarter
Hält's aus hier
Beiträge: 10



BeitragVerfasst: So 08.10.06 15:55 
cool, ich muss mich noch reindenken, aber das sieht erstma klasse aus und funktioniert auch.
DANKE!!!
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: 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.
ausblenden Delphi-Quelltext
1:
Kombination ('1234','',1,2,[]); // <--- n=4, k=2					

Im Prinzip ist das doch das Gleiche wie bei Horst_H.

_________________
Na denn, dann. Bis dann, denn.