"ABCD" in allen möglichen Kombinationen

[-lx-]

Hallo.


Und zwar meine Aufgabe ist es ein Programm zu schreiben, das nach der Eingabe eines n langen Strings alle möglichen Kombinationen ausspuckt, wie man "ABCD" schreiben könnte.

Ich hab mich hingestezt und verschiedene Varianten ausprobiert, um ein System rauszubekommen, wie man am Besten alle Kombis erhält.

Bei folgender Methode (die ich mir ausgedacht habe) bin ich stehen geblieben:

A B C D
A B D C
A D B C
A D C B
A C D B
A C B D
C A B D
C A D B
C D A B
C D B A
C B D A
C B A D
B C A D
B C D A <---
B D C A
B D A C
B D C A
....

nur jetzt komme ich mit meiner Variante nicht mehr weiter. Nach meienm System müsste nun wieder BCDA kommen. Die shatten wir jedoch schon.

Wie also kann ich das anders angehen bzw. wie spielt man alle möglichen Varianten am Besten durch?


Einfach eine Quelltext mir anzuschaun wäre in dem Fall - meines Ermessens - nicht sinnvoll.



Also kann mir wer nen Tipp geben wie ich das anpacken könnte?





Mit freundlichen Grüßen

Alex

[Sunlight7]

Hallo,

Du könntest die Werte die Du bereits hast zuerst überprüfen, und nur dann hinzufügen, wenn der neue Wert noch nicht dabei ist.
Das ist dann zwar kein perfektes Programm, aber ein perfektes würde Dir der Lehrer wohl nicht abkaufen. :zwinker:

Zeig mal Deinen Quelltext, wie Weit Du bist, wenn Du hilfe möchtest.

[marabu]

Hallo Alex,

hier ein thread zum Thema mit vielen Code-Beispielen und weiterführenden Links: klick

Grüße vom marabu

[Amateurprofi]

Das machst Du so :
1) Du markierst das Wort "Kombinationen"
2) Du drückst Strg und C
3) Du klickst "Suchen" unterhalb der Titel-Leiste
4) Du klickst das Eingabefeld "nach Begriffen suchen"
5) Du drückst Strg und V (oder tippst "Kombinationen" ein.
6) Du klickst "Suchanfrage absenden.

Dann wirst Du unter den erste 10 Einträgen einen Verweis auf einen Beitrag finden, der das Problem behandelt.

[dino]

nun binär zählt man:
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

dem entsprechend würde ich so vorgehen:
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

wie hab ich das gemacht, nach welchem Prinzip bin ich vorgegangen und wie kann ein Programm das reproduzieren?

[-lx-]

Hallo,


und danke für eure Antworten. Werde mich erstmal durch das Thema von Wikipedia arbeiten (http://de.wikipedia.org/wiki/Kombinatorik).

Ohne jedoch zu wissen, was in diesem Artikel steht, stelle ich noch eine Frage (auch wnen diese vll. in dem Artikel beantwortet wird):

Wie spiele ich denn alle möglichen Kombinationen von Wörtern durch?
Ich meine nach welchen Regeln? Da muss es doch etwas geben was zumindest eien gewissen Systematik dort rein bringt.
Denn wenn ich weis wie ich alle Kombinationen durch spinne, und dies ien System hat, kann ich es wohl auch einfacher rekursiv als Algorythmus übersetzen.

-----------------------------
€dit:/ Es wäre vll. auch möglich mit Hilfedes "Zuafalls" alle mäglichen Kombinationen herauszubekommen, aber die sist wohl ser unelegant und nicht gerade zuverlässig. Die Anzahl der Kombination wäre ja n-Fakultät (n!).
-----------------------------


Nungut... jetzt muss ich mich erstmal wieder der Zellteilung, der DNA-Replikation und dem Aufbau der DNA witmen.




Einen schönen Abend noch! =)






mit freundlichen Grüßen

Alex

[dino]

bei einem Wort von 7 Buchstaben: (1234567)

1234567
1234576
1234657
1234675
1234756
1234765
1235467
1235476
1235647
1235674
1235746
1235764
1236457
1236475
1236547
1236574
1236745
1236754
1237456
1237465
1237546
1237564
1237645
1237654
124

und so weiter und so fort
eine frage:

"1234567" hat 7! verschiedene Möglichkeiten, während bei
"Kindern" das n 2 mal vorkommt wodurch einige Kombinationen doch gleich sind

wenn die wirklich unterschiedlich sein sollen, hab ich auch keine Idee mehr ansonsten hätte ich zunächst ignoriert, wie die einzelnen Buchstaben tatsächlich aussehen und systematisch alles agezeigt

[3_of_8]

Na so schwer ist das doch wieder auch nicht... Man braucht einmal einen Bitvektor mit den bereits benutzten Zahlen und muss das dann einfach immer wieder richtig setzen.

So kannst du prima durchpermutieren.

Sobald man mehr als 11 Zeichen hat, reicht der Speicher allerdings nicht mal mehr annähernd. Schon 11 Zeichen sind kritisch.

[dino]

hab da was Programmiert für ein Wort mit 7 Buchstaben

Delphi-Quellcode:

var i1,i2,i3,i4,i5,i6,i7:Integer;
begin
s:=edit1.text;
for i1:=1 to 7 do
for i2:=1 to 7 do
if i1<>i2 then
for i3:=1 to 7 do
if (i1<>i3)and(i2<>i3) then
for i4:=1 to 7 do
if (i1<>i4)and(i2<>i4)and(i3<>i4) then
for i5:=1 to 7 do
if (i1<>i5)and(i2<>i5)and(i3<>i5)and(i4<>i5) then
for i6:=1 to 7 do
if (i1<>i6)and(i2<>i6)and(i3<>i6)and(i4<>i6)and(i5<>i6) then
for i7:=1 to 7 do
if (i1<>i7)and(i2<>i7)and(i3<>i7)and(i4<>i7)and(i5<>i7)and(i6<>i7) then
listbox1.Items.add(s[i1]+s[i2]+s[i3]+s[i4]+s[i5]+s[i6]+s[i7]);

[-lx-]

@ Dino

Ich denke das smit doplleten Buchstaben kann man vorerst vernachlässigen. Jediglich später beim "feintuning" kann man das überprüfen.

Aber ich hab nicht ganz verstanden wie du das mit dem Binärsystem meinst. Binär kann ich zählen nur wie überträgst du das auf eien Zeichenfolge?





mfg

[3_of_8]

Er spricht von einer simplem Permutation.

Achja, dazu gibt es CodeLib-Einträge.

Permutation

[-lx-]

Hallo,


also mir ist das Prinzip von dino noch immer nicht klar.

A B C D
A B D C
A C B D <--- wieso ? Wieso nicht A D B C ?



also mir ist der Mechanismus noch nicht klar, wie man man denn beim Vertauschen vor geht. Man kann doch nicht einfach willkürlich tauschen. Es müsste ja eig. immer schrittweise gehen - rekursiv eben.

[dino]

Zitat:

Zitat von -lx-

A B C D
A B D C
A C B D <--- wieso ? Wieso nicht A D B C ?

weil ich von links nach recht immer den kleinstmöglichsten Buchstaben nehme, dessen Kombination nch nicht vorgekommen ist :)

[alzaimar]

Also, ich habe eine Liste, die ich in allen möglichen Kombinationen zusammenstellen will.
Na denn:

Code:

Erzeuge alle Permutationen (Liste L, bisherige Lösung)
Für jedes Element E in der Liste L
  Wenn E noch nicht in der bisherigen Lösung enthalten ist, dann
      Wenn E das letzte noch nicht verwendete Element der Liste ist, dann
         Ist [Lösung + E] eine Permutation
      ansonsten
         Erzeuge alle Permutationen (L, Lösung + E)

Das ist übrigens schon fast die fertige rekursive Routine. Wenn Du das verstanden hast, kannst du es auch implementieren.

[-lx-]

Hab heute den Vater meiner Freundinn auch nochmal gefragt, wie man denn sowas anpackt. Und er hat es mir auch so erklärt, wie Dino es angesprochen hat.

Nur hab ich es bei ihm besser verstanden. Warscheinlich weil eien direkte Konversation mehr bringt als was geschriebenes. Nichst gegen euch =)


Ich danke euch für eure mühen. Ihr werden in den nächsten Postings dann meien Programmieransätze sehen ! :)




mit freundlichen Grüßen

[Cöster]

Das hat mir jetzt keine Ruhe gelassen :stupid:

Hier mein Quellcode:

Delphi-Quellcode:

function TForm1.Factorial(const x: Byte): Word;
begin
  if x > 1 then
    result := x * Factorial(x - 1)
  else
    result := x;
end;

procedure TForm1.CalcNextS(var s: string; const Initial: string);
var
  l: Byte; // Position linker Austauschpartner
  r: Byte; // Position rechter Austauschpartner
  i: Byte; // Laufvariable
  Done: Boolean; // für Bubblesort
  Temp: Char;
begin

  // linken Austauschpartner finden
  l := Length(s);
  repeat
    Dec(l);
  until Pos(s[l], Initial) < Pos(s[l+1], Initial);

  // rechten Austauschpartner finden
  r := l + 1;
  for i := l to Length(s) do
    if (Pos(s[i], Initial) > Pos(s[l], Initial)) and
      (Pos(s[i], Initial) < Pos(s[r], Initial)) then
        r := i;

  // austauschen
  Temp := s[l];
  s[l] := s[r];
  s[r] := Temp;

  // rechts von l der Größe nach sortieren
  if l <> Length(s) - 1 then
    repeat
      Done := True;
      for i := l+1 to Length(s) - 1 do
        if Pos(s[i], Initial) > Pos(s[i+1], Initial) then
        begin
          Temp := s[i];
          s[i] := s[i+1];
          s[i+1] := Temp;
          Done := False;
        end;
    until Done;

end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
  s: string;
begin
  ListBox1.Clear;
  s := Edit1.Text;
  ListBox1.Items.Add(s);
  for i := 2 to Factorial(Length(s)) do
  begin
    CalcNextS(s, Edit1.Text);
    ListBox1.Items.Add(s);
  end;
end;

Das Wort kann aus bis zu 255 Zeichen bestehen. Ich hab allerdings noch nicht berücksichtigt, dass Buchstaben auch mehrfach vorkommen können.

Die .exe ist im Anhang

[Cöster]

Zitat:

Zitat von Cöster

Das Wort kann aus bis zu 255 Zeichen bestehen. Ich hab allerdings noch nicht berücksichtigt, dass Buchstaben auch mehrfach vorkommen können.

Äh, nee, kann doch nur aus 12 Buchstaben/Zahlen bestehen, weil die Fakultät sonst nicht mehr in den Integerrahmen passt. Es braucht bei 8 Zeichen aber auch schon ca. 6 Sekunden, bei 9 über ner Minute, ein Progressbar wär wohl angebracht.

Dass Zeichen sich wiederholen können, hab ich jetzt auch gelöst: Bevor nach Kombinationen gesucht wird, werden die Zeichen sortiert. Pro Zeichen, welches x-mal hintereinander vorkommt, wird die Anzahl der Kombinationen dann durch x! geteilt.

[3_of_8]

Genaugenommen kann ein String theoretisch bis zu 2 (oder warens 4) GiB groß sein.

[dino]

meins ist zwar nur für 7 Zeichen, aber ungefähr gleich schnell

[Cöster]

Zitat:

Zitat von 3_of_8

Genaugenommen kann ein String theoretisch bis zu 2 (oder warens 4) GiB groß sein.

Ja, aber wenn der String aus 13 verschiedenen Zeichen besteht, gibt es 13!, also 6227020800, Kombinationsmöglichkeiten. Das ist für die ListBox zu viel, die Funktion Factorioal geht auch nur bis zur Integergrenze und außerdem würde die Berechnung über 2 Wochen dauern. Bei 12 Zeichen würde es wahrscheinlich "nur" knapp über einem Tag dauern und die beiden anderen Probleme gäb's auch nicht.

[3_of_8]

Ich würde mal sagen, ein solcher Algorithmus sollte schon generisch sein.

Und im allgemeinen kann man sagen: Schneller als von Hagen gehts ned.

@Cöster: Ja, ich weiß. Das hab ich ja gleich gesagt. Aber die Aussage, ein String könne nur 255 Zeichen lang sein, stimmt auch nicht. Jedenfalls nur für ShortStrings, also diese alten Dinger.

[Cöster]

Zitat:

Zitat von 3_of_8

Aber die Aussage, ein String könne nur 255 Zeichen lang sein, stimmt auch nicht.

Hab ich das gesagt?

Zitat:

Zitat von Cöster

Das Wort kann aus bis zu 255 Zeichen bestehen.

Code:

if Ein String = Das Wort then
  ich hab gelogen
else
  hab ich auch nie gesagt

@ Dino: Bei mir ist meine Variante ca. doppelt so schnell wie deine. :mrgreen: Aber bei 7 Zeichen ist die Geschwindigkeit ja sowieso nicht so wichtig.

Fliegt der Code von Hagen hier auch irgendwo im Forum rum? Würd mich mal interessieren. Können normal Sterbliche den überhaupt verstehen?

[negaH]

also, schneller gehts immer, es gibt immer andere Programmierer die noch mehr drauf haben als man selber drauf hat. Ich verwehre mich also hiermit ausdrücklich das meine Codes die schnellsten sein müssen. Allerdings bin ich schon ein Freak der den Ehrgeiz hat den bestmöglichen Algorithmus zu finden, und dabei natürlich ne Menge lernen möchte. Das impliziert aber eben nicht das meine Codes die schnellsten sein müssen. Auf Alzaimar, Olliver oder NicoDE und auf die viele Anderen hier würde die gleiche Aussage auch zutreffen.

http://www.delphipraxis.net/internal...561&highlight=

Es findet sich hier in der DP aber auch eine Lösung von Alzaimar die ich persönlich als sehr elegant empfinde und die mindestens genauso effizient sein muß wie die meinige. Einfach mal suchen.

Zitat:

Können normal Sterbliche den überhaupt verstehen?

Nöö, natürlich nicht, ich bin ja anscheinend unsterblich. Nur merke ich die letzten 2 Wochen davon nichts, sonst würde ich nicht auf Grund meiner derzeitgen Bronchitis nicht ständig am Husten sein (Raucher) ;) Klar wirst du ihn verstehen du musst dich halt nur intensiv damit beschäftigen wollen.

Gruß Hagen

[alzaimar]

Um mal meinen Senf dazuzugeben, hier die kurze Version. Ich find sie auch elegant, vor allen Dingen, weil Sie als Abfallprodukt eines anderen Problems enstanden ist. Davor habe ich mich mit Inversen und Graycodes beschäftigt, um Permutationen zu erzeugen, aber das ist ein anderes Thema.

Delphi-Quellcode:

Type
  TCharSet = Set Of Char;

Procedure TForm1.Permutation(Const aString, aResult : String; anIndex : Integer; aUsedChars : TCharSet);
Var
  i : Integer;

Begin
  For i:=1 to Length (aString) do
    if not (aString[i] in aUsedChars) then
      If anIndex = Length (aString) Then
        Memo1.lines.add(aResult+aString[i])
      Else
        Permutation (aString, aResult + aString[i], anIndex + 1, aUsedChars + [aString[i]]);
End;

Aufruf mit

Delphi-Quellcode:

Permutation (edit1.Text, '',1, [])

Der Algorithmus versagt allerdings, wenn ein in einem Wort ein Zeichen doppelt vorkommt, aber das sind dann klassisch gesehen keine Permutationen, denn die basieren ja auf einer Menge von Zeichen. Und in einer Menge gibts keine doppelten Elemente (gott-sei-dank).

Ein Wort noch zu der Performance. Bei diesem Minimalalgorithmus habe ich bewusst darauf verzichtet, den Flaschenhals "Stringkonkatenation" wegzuoptimieren. Das Problem ist ja der rekursive Aufruf, in dem eine Konkatenation steht.
Ein winziger Test bestätigt allerdings, das der Geschwindigkeitszuwachs marginal ist. Erst bei Wortlängen>7 ist überhaupt eine Verzögerung spürbar und dann geht der Performancegewinn schon gegen 0.

Viel wichtiger ist der Container, der die Permutationen aufnehmen soll. Eine Stringliste wie hier (womöglich noch als visuelles Element) ist sowieso die größte Bremse. Besser ist ein dynamisches Array, das vorher auf die korrekte Länge (N!) gesetzt wird.

Ich kann mir allerdings keinen Fall vorstellen, bei dem man zunächst alle Permutationen erzeugt, um sie dann -wie auch immer- zu verarbeiten. Normalerweise lässt sich ein solches Problem viel eleganter (und damit meist auch performanter) lösen.

[-lx-]

Hallo.


Nach langem informieren, überlegen und ein wneig lunzen auf andere Codes hab ich nun etwas zu stande gebarcht bzw. zu "Papier".

Ich will euch dne Code nicht vorenthalten, jedoch läuft er noch nicht einbahnfrei. Sprich: Er gibt was aus aber noch das falsche.

Da mir die Lösung erst um 12 Uhr (24 Uhr Ortszeit) eingefallen ist, hab ich nun nicht mehr die Kraft alles durhc zu spinnen und zu überlegen wo der Haken liegt.

Wer mag kann sich diesen NOCH FEHLERHAFTEN Code anschaun und vll. auch mal kurze Hilfestellung geben ;)

Delphi-Quellcode:

procedure Permutation(n: Integer; const Text: String) ;
    var i: Integer ;
        CopyText, Neu: String ;
        begin
          CopyText:= Text ;
          For i:= n To length(CopyText) Do
              begin
                If length(CopyText) >= 1 Then
                    begin
                      showmessage('hallo');
                      Neu:= Neu + CopyText[i] ;
                      Delete(CopyText, i, 1) ;
                    end
                Else
                    begin
                      Neu:= Neu + CopyText[i] ;
                      Memo1.Lines.Add(Neu) ;
                    end;
                If n < length(CopyText) Then Permutation(n+1, Text) ;
                Memo1.Lines.Add(Neu) ;
              end;

        end;

Gute Nacht alle miteinder :)


//Edit: Ich merke, da ist noch einiges an Verbesserung nötig ...