Autor |
Beitrag |
MisterAHA
      
Beiträge: 16
|
Verfasst: Di 28.10.08 23:41
Hallo Leute,
ich bin auf ein "Problemchen" gestoßen, dass ich nun schon seit fast 2 Wochen versuche zu lösen, ich aber einfach nicht voran komme.
Ich versuche rechentechnisch alle Kombination einer Binominalverteilung zu bekommen. Dabei interessiert mich weniger der Binominalkoeffizient, sondern alle möglichen Kombinationen die dabei entstehen.
zb. A B C => A,B,C,AB,AC,BC,ABC ...ihr versteht?
ich bin echt am verzweifeln :-/
Vielleicht habt ihr ja einen guten Vorschlag!?
mfg Andreas
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mi 29.10.08 04:25
Da Du wie es scheint, alle Kombinationen haben willst, ohne Beachtung der Reihenfolg, kann man das recht kurz etwa so skizzieren:
Python-Style Pseudo-Code: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| Betrachte alle möglichen Buchstaben A,B,C als String 'ABC' Für alle Längen: Z[0] = 0; P = 0; Solange Z[0] == 0 Solange P < Länge && Z[P] + (Länge-P) <= Länge P++; Z[P] = Z[P-1] + 1; Wenn P = Länge Kombination ausgeben (Z[1]..Z[Länge]) Z[P]++; Wenn Z[P] > AnzahlZeichen && P > 0 P--; Z[P]++; |
Das Übersetzen in ausführbaren Delphi-Code überlass ich mal dem Fragesteller 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
MisterAHA 
      
Beiträge: 16
|
Verfasst: Mi 29.10.08 21:28
ich hab mich jetzt mal mit meinem kollegen hingesetzt, und deinen vorschlag ausprogrammiert.
leider ohne erfolg. es wird nur eine kombination ausgeben. wir brauchen aber dringen alle kombinationen.
|
|
Jann1k
      
Beiträge: 866
Erhaltene Danke: 43
Win 7
TurboDelphi, Visual Studio 2010
|
Verfasst: Mi 29.10.08 21:48
Zitat: |
ich hab mich jetzt mal mit meinem kollegen hingesetzt, und deinen vorschlag ausprogrammiert.
leider ohne erfolg. es wird nur eine kombination ausgeben. wir brauchen aber dringen alle kombinationen. |
Dann wäre jetzt der richtige Zeitpunkt, um uns den relevanten Abschnitt aus eurem Quelltext vorzustellen. Ohne Quelltext kann man nur schwer sagen woran es liegt. Wäre auch interessant zu wissen, wie die Ausgabe erfolgen soll (in ein array, eine Tstringlist...).
|
|
MisterAHA 
      
Beiträge: 16
|
Verfasst: Mi 29.10.08 22:21
..ich habe gerad in einem anderem forum einen entsprechenden code gefunden:
nur wie müsste der ausschauen, wenn die bildung der permuationen OHNE zurücklegen funktionieren soll?
:-/
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:
| procedure CombiStrings(const Values: array of String; Permutation: Boolean = True); overload;
type PPCharArray = array of PChar;
var Patterns: PPCharArray;
procedure DoPrint; var I: Integer; begin for I := 0 to High(Patterns) -1 do Write(Patterns[I], ','); WriteLn(Patterns[High(Patterns)]); end;
procedure DoCombi(Start, Stop: Integer); var Pos: Integer; Tmp: PChar; Last: String; begin if Start >= Stop then begin DoPrint; Exit; end; Last := ''; Pos := Start; while Pos <= Stop do begin Tmp := Patterns[Pos]; Patterns[Pos] := Patterns[Start]; Patterns[Start] := Tmp; if not Permutation or (AnsiCompareText(Tmp, Last) > 0) then begin DoCombi(Start +1, Stop); Last := Tmp; end; Inc(Pos); end; Tmp := Patterns[Start]; while Start < Stop do begin Patterns[Start] := Patterns[Start +1]; Inc(Start); end; Patterns[Start] := Tmp; end;
procedure DoCreate; var I,J,K: Integer; begin SetLength(Patterns, Length(Values)); for I := 0 to High(Values) do begin J := 0; while (J < I) and (AnsiCompareText(Values[I], Patterns[J]) > 0) do Inc(J); for K := I -1 downto J do Patterns[K +1] := Patterns[K]; Patterns[J] := PChar(Values[I]); end; end;
begin DoCreate; DoCombi(0, High(Patterns)); end; |
Moderiert von Christian S.: Delphi-Tags hinzugefügt
|
|
Jann1k
      
Beiträge: 866
Erhaltene Danke: 43
Win 7
TurboDelphi, Visual Studio 2010
|
Verfasst: Mi 29.10.08 22:24
Pack den Quelltext bitte in delphi-tags (delphi) Quelltext (/delphi) (Eckige Klammern statt runde) so kann/will den nämlich kaum jemand lesen
|
|
MisterAHA 
      
Beiträge: 16
|
Verfasst: Mi 29.10.08 22:27
sorry, ich vergaß
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:
| procedure CombiStrings(const Values: array of String; Permutation: Boolean = True); overload;
type PPCharArray = array of PChar;
var Patterns: PPCharArray;
procedure DoPrint; var I: Integer; begin for I := 0 to High(Patterns) -1 do Write(Patterns[I], ','); WriteLn(Patterns[High(Patterns)]); end;
procedure DoCombi(Start, Stop: Integer); var Pos: Integer; Tmp: PChar; Last: String; begin if Start >= Stop then begin DoPrint; Exit; end; Last := ''; Pos := Start; while Pos <= Stop do begin Tmp := Patterns[Pos]; Patterns[Pos] := Patterns[Start]; Patterns[Start] := Tmp; if not Permutation or (AnsiCompareText(Tmp, Last) > 0) then begin DoCombi(Start +1, Stop); Last := Tmp; end; Inc(Pos); end; Tmp := Patterns[Start]; while Start < Stop do begin Patterns[Start] := Patterns[Start +1]; Inc(Start); end; Patterns[Start] := Tmp; end;
procedure DoCreate; var I,J,K: Integer; begin SetLength(Patterns, Length(Values)); for I := 0 to High(Values) do begin J := 0; while (J < I) and (AnsiCompareText(Values[I], Patterns[J]) > 0) do Inc(J); for K := I -1 downto J do Patterns[K +1] := Patterns[K]; Patterns[J] := PChar(Values[I]); end; end;
begin DoCreate; DoCombi(0, High(Patterns)); end; |
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Mi 29.10.08 22:41
Solange es nicht mehr als 64 Elemente sind, sollte es sich kurz auch mit Delphis Set-Interpretation lösen lassen: Jedem Element wird ein Bit eines Int64 zugeordnet. Den dann von 1 bis 2^n-1 laufen lassen, fertig.
F# 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| #light open System
let charCombinations (s:String) = let n = s.Length seq { for i in 1..(1<<<n)-1 do yield seq { for j in 0..n-1 do if (1<<<j) &&& i <> 0 then yield s.[j] }} > charCombinations "ABCD" |> Seq.map (fun a -> String(Seq.to_array a)) |> Seq.to_list;; val it : String list = ["A"; "B"; "AB"; "C"; "AC"; "BC"; "ABC"; "D"; "AD"; "BD"; "ABD"; "CD"; "ACD"; "BCD"; "ABCD"] | Die Übersetzung wird dem geneigten Leser überlassen  .
[add]
Gut, der allgemeine Fall lässt sich mit Rekursion fast noch schöner lösen:
F# 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| let combinations xs = let rec loop acc = function | [] -> Seq.singleton acc | x::xs -> Seq.append (loop acc xs) (loop (x::acc) xs) loop [] xs |> Seq.skip 1
> combinations (Seq.to_list "ABCD") |> Seq.map (fun a -> String(Seq.to_array a)) |> Seq.to_list;; val it : String list = ["D"; "C"; "DC"; "B"; "DB"; "CB"; "DCB"; "A"; "DA"; "CA"; "DCA"; "BA"; "DBA"; "CBA"; "DCBA"] |
Ggf. das Ergebnis noch umdrehen  .
_________________ >λ=
Zuletzt bearbeitet von Kha am Mi 29.10.08 23:13, insgesamt 1-mal bearbeitet
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mi 29.10.08 23:13
Das Delphi-Set sollte bis 255 Elemente schaffen.
Aber der Source von dem Kollegen was ihr da gebaut hattet, würd mich auch mal interessieren. Weil das ist wesentlichen nmlich meine Lösung zu einem der letzten Paranussrätsel gewesen ... Nur, dass es da um ein TSP ging 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Mi 29.10.08 23:27
BenBE hat folgendes geschrieben : | Das Delphi-Set sollte bis 255 Elemente schaffen. |
Kann schon sein, aber da man noch eine Schleifenvariable braucht, wird man ohne große Umwege bei 64 Bit stecken bleiben. Und mittlerweile gefällt mir mein Rekursionsansatz sowieso viel besser  .
BenBE hat folgendes geschrieben : | Aber der Source von dem Kollegen was ihr da gebaut hattet, würd mich auch mal interessieren. Weil das ist wesentlichen nmlich meine Lösung zu einem der letzten Paranussrätsel gewesen ... |
Irgendeine Chance, dass ich von deinem Algo mehr als [leere Menge] verstehe  ?
_________________ >λ=
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 30.10.08 00:48
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Do 30.10.08 01:26
Letztendlich entspricht das der Suche nach allen Teilmengen der Menge {A, B, ..., X}, oder?
Das sollte doch relativ leicht rekursiv zu lösen sein...
Bis auf die Laufzeit halt 
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 30.10.08 03:05
Erledige nichts rekursiv, dessen Rekursionstiefe mit der Problem-Komplexität korrelliert 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Do 30.10.08 11:33
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 30.10.08 13:20
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Do 30.10.08 13:40
|
|
BenBE
      
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Do 30.10.08 13:46
Bei QucikSort heißt das aber u.U. auch, dass das Teil quadratisch ist  Dann doch lieber garantiert langsam - wie z.B. MergeSort 
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Thorsten83
      
Beiträge: 191
Erhaltene Danke: 1
|
Verfasst: Fr 31.10.08 16:44
|
|
|