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
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,[]); End; |
Reinhard Kern - So 08.10.06 11:24
Titel: Re: Algorithmus zum Ausgeben aller Kombinationen
mr.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
Reinhard 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!
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 public end;
var Form1: TForm1;
implementation
{$R *.dfm}
function NUeberK(n,k:integer):int64; var i : integer; begin result := 1; i := 1; while i<=K do begin result := result*n div I; 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 outString := outString+RestString[i]; l := length(RestString); Reststring[i] := Reststring[l]; setlength(Reststring,l-1);
IF k>1 then NUeberKKomb(outString,Reststring,k-1) else 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
mr.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,[]); |
Im Prinzip ist das doch das Gleiche wie bei Horst_H.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!