Permutation (mögliche Kombinationen)

[juniorA]

Moin, moin,
Ich habe eine Menge von Teilen (max. 100 Stück), welche ich miteinander kombinieren will um zu testen ob bestimmte Kriterien eingehalten werden.
Wenn ich mich so richtig erinnere hat dieses etwas mit Permutationen zu tun.
Kennt einer einen brauchbaren Algorithmus, welcher alle möglichen Kombinationen ausgibt wenn N Werte zur Verfügung stehen. Wenn N z.B. 5 ist, sollen alle Kombinationen ausgegeben werden welche die Buchstaben ABCDE ergeben können.
In jeder Kombination darf ein Buchstabe nur einmal vorkommen.

[mkinzler]

http://www.schule-bw.de/unterricht/f...mbinatorik.pdf

[smallie]

Da gibt es n! Kombinationen.

Ich befürchte, daß mehr als n zwischen zehn und zwanzig aus Laufzeitgründen nicht mehr geht.

[gammatester]

Gibt's als Algorithmen bei Knuth.

Für Permutationen http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
und für Kombinationen http://www-cs-faculty.stanford.edu/~uno/fasc3a.ps.gz
oder für Klick-Klack-Techniker von http://rosettacode.org/wiki/Permutations#Delphi
bzw http://rosettacode.org/wiki/Combinations#Pascal

[Jens01]

@gammatester (bezieht sich auf die ersten beiden links)

[jobo]

Das ist vielleicht ein schönes Thema für SQL (Daten-Mengen), Kreuzprodukte, ..
Sobald man 2. Mengen vereint und keine geeigneten Join Kriterien festlegt, permutiert es quasi von allein.

[juniorA]

Ich habe mir jetzt einmal einen Teil des Codes geladen und angepasst. Das Problem mit der Laufzeit bei Kombinationen mit mehr als 6 Zeichen ist da. Ich habe aber noch eine anderes Problem und zwar gibt es bei mehr als 11 Zeichen einen Integerüberlauf.

Delphi-Quellcode:

procedure Form1.Button1Click(Sender: TObject);
{$APPTYPE CONSOLE}

const anz_c : integer = 12;

type
  TItem  = char;
  TArray = array[0..12] of TItem;


procedure Permutation(K: Integer; var A: TArray);
var
  I, J : Integer;
  Tmp  : TItem;

begin
  for I:= 1 to (anz_c + 1) do
  begin
    J     := K mod I;
    Tmp   := A[J];
    A[J]  := A[I-1];
    A[I-1]:= Tmp;
    K     := K div I;
  end;
end;

var
  A                : TArray;
  I, K, Count, anz : Integer;
  S, S1, S2        : ShortString;
  Source           : TArray;

begin
  for I := 0 to anz_c do source[i] := chr(65+i);

  Count:= 1;
  anz  := 0;
  I:= Length(A);
  while I > 1 do
  begin
    Count:= Count * I;
    Dec(I);
  end;

  S:= '';
  for K:= 0 to Count - 1 do
  begin
    A:= Source;
    Permutation(K, A);
    S1:= '';

    for I:= 0 to anz_c do
    begin
      s2 := A[I];
      S1:= S1 + S2;
    end;

    inc(anz);
    S:= S + ' ** ' + S1;
    if Length(S) > 40 then
    begin
      Writeln(S);
      S:= '';
    end;
  end;

  if Length(S) > 0 then Writeln(S);
  writeln('Anz : ', anz);
  Readln;

end;

Ideen gesucht

[Dejan Vu]

Zitat von jobo:

Das ist vielleicht ein schönes Thema für SQL (Daten-Mengen), Kreuzprodukte, ..
Sobald man 2. Mengen vereint und keine geeigneten Join Kriterien festlegt, permutiert es quasi von allein.

Äh, nee. Wie bekommt man denn die Permutationen von '123' mit SQL hin? Oder reden wir von allen 3-stelligen Wörtern des Alphabetes ('1','2','3')? Ein Cross join liefert dir wirklich alle Kombinationen, aber hier steht was von 'Permutation' und wenn das mit SQL geht, fress ich ... ach nee, das geht ja...

Ach, hier noch eine kleine Routine:

Delphi-Quellcode:

Procedure Perm (Const aString : String);
  Procedure _Perm (Const aPrefix, aString : String);
  Var
    i,len : Integer;

  Begin
    len  := Length (aString);
    If len = 1 Then
      Log (aPrefix+aString)
    Else For i:=1 to l do
      _Perm (aPrefix+aString[i], Copy (aString,1,i-1)+Copy (aString,i+1,l-i));
  End;

Begin
  _Perm ('',aString);
End;

Diue Prozedure 'Log' musst Du selbst schreiben (Ausgabe in Memo, speichern in Stringlist o.ä.)

[jobo]

@dejan vu:
Das ist eine Frage der Abbildung der Werte. Wenn alles in einem Feld steht, ist es eine blöde Frickelei. Ähnliche wie bei 27 For Schleifen mit Integer-Überlauf.
Es ist vielleicht nicht Ressourcen schonend, aber bequem, schnell gemacht und flexibel.

[BUG]

Je nach Art der Kriterien kannst du den Suchraum vielleicht auch einschränken. Da kommt es dann auf die Details an.