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 :-D (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 :cry:

[Dejan Vu]

Zitat:

Zitat von jobo (Beitrag 1262468)

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.

[juniorA]

So richtig kann ich damit leider nichts anfangen.
Was ich suche ist eigentlich ein Generator der mir bei einer Vorgabe von n möglichen Eingangswerten alle möglichen Kombinationen dieser n Eingangswerte wiedergibt.
Maximal können dieses 99 Eingangswerte sein. Bis 11 Eingangswerte ging dieses gut, aber dann gab es dieses Problem.

[Dejan Vu]

Zitat:

Zitat von juniorA (Beitrag 1262517)

...alle möglichen Kombinationen...

Meinst Du Permutation, Kombination oder Variation oder einfach alle Zahlen zur Basis 'P'?
Was soll bei drei Eingabewerten herauskommen, die die Werte A, B oder C annehmen können?
Was erwartest Du eigentlich bei 99 Eingabewerten? Was machst Du mit den Ausgaben? Wie lange willst Du warten?

[Bjoerk]

Zitat:

Zitat von juniorA (Beitrag 1262517)

Bis 11 Eingangswerte ging dieses gut, aber dann gab es dieses Problem.

Müßte bis 12! gehen. Erst 13! ist größer MaxInt.

[Medium]

Bei n=99 wird es ein Ergebnis von rund 93326215443944152681699238856267000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 000000 Datensätzen geben (laut Windows Taschenrechner, und wenn ich bei den Nullen nicht 1-2 falsch gezählt habe - aber eh unwichtig). Wenn jedes der 99 Elemente ein Byte groß ist, wird das Ergebnis grob 84030901497958176291724381797125000000000000000000 00000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000 Terabyte umfassen. (Ebenfalls die gleiche Unsicherheit mit den Nullen, aber auch hier ziemlich egal.)

So.

Selbst wenn man es so machen würde, dass man nicht alle Ergebnise vorab speichert (was diverse Erden an Gesamtkapazität aller je gebauten Speichermedien konsumieren dürfte...), müsste man diese dennoch alle durchprüfen. Selbst wenn man dies jetzt bloß auf den Datendurchsatz aktuellen DDR3 RAMs berechnen würde, kann ich mir gut vorstellen, dass man das Endergebnis der Auswertung ungefähr kurz vor der Supernova unserer Sonne ablesen könnte. So ganz grob geschätzt.

Fazit: Entweder du kannst Einschränkungen machen, oder das Vorhaben ist von Anfang an komplett und vollständig, ohne Wenn und Aber, schlicht und ergreifend unmöglich. Ein Integer-Überlauf ist hier mit sicherheit das kleinste aller Probleme.

[juniorA]

Ist einleuchtend.
Danke für die Antwort.
Vielleicht gibt es nächsten Jahrtausend eine Antwort darauf.

Zwischenspeichern muss ich übrigens immer nur eine Variante (Kombination), da ich mit jeder Ausgabe einer Kombination teste ob sie bestimmte Kriterien erfüllt. Die Variante (Reihenfolge der Werte) die am dichtesten am Ziel liegt wird sich gemerkt.
Wenn eine bessre gefunden ist, wird die alte überschrieben.

[p80286]

Das erinnert mich irgendwie an affen und Schreibmaschinen

Gruß
K-H

[Sir Rufo]

Zitat:

Zitat von juniorA (Beitrag 1262613)

Ist einleuchtend.
Danke für die Antwort.
Vielleicht gibt es nächsten Jahrtausend eine Antwort darauf.

Zwischenspeichern muss ich übrigens immer nur eine Variante (Kombination), da ich mit jeder Ausgabe einer Kombination teste ob sie bestimmte Kriterien erfüllt. Die Variante (Reihenfolge der Werte) die am dichtesten am Ziel liegt wird sich gemerkt.
Wenn eine bessre gefunden ist, wird die alte überschrieben.

Dann machen wir mal ein wenig Robert Lemke, wenn du uns die Informationen so nicht geben möchtest :roll:

Gehe ich recht in der Annahme, dass jedes Element in einer Kombination nur einmal auftauchen darf?

Code:

Menge (1,2,3,4)
gültig sind (1,2), (1,3), (1,2,3)
ungültig sind (1,1), (1,2,2)

Wenn du die beste Kombination haben möchtest, warum willst du dann erst alle Kombinationen zusammenbauen?
Wenn (1,2) die Kriterien nicht erfüllt und man weiß, dass diese Kombination auch nicht besser wird, wenn die mit einem anderen Element kombiniert wird, dann kann man diese Kombinationen schon mal komplett ausnehmen und spart sich eine Menge weiterer Prüfungen.

[Dejan Vu]

Das nennt sich 'pruning', das der Traversierungsbaum beschnitten (engl: to prune) wird. Wenn man z.B. weiß, das (1,2) vollkommener Schrott ist und auch (1,2,x,y,z...) dann kann man getrost alle Derivate ignorieren. So wird in der klassischen Spieletheorie der Suchbaum (Schach z.B.) drastisch verkürzt.

Aber da der Fragesteller wohl selbst nicht weiß, was er will und Fragen nicht beantworten kann, soll er halt weiter friemeln.

[BUG]

Vielleicht braucht man ja auch nicht suchen, sondern kann das Ergebnis konstruieren. Wer weiß?
Ohne ein wenig Details zu Bedingungen kann man noch nicht mal versuchen, eine ordentliche Vermutung anstellen.

Wenn du wirklich nichts verraten willst oder das Problem zu kompliziert ist und das Problem nicht unbedingt mit Delphi lösen musst, kannst du dir mal Prolog (oder Verwandte davon) angucken. Die gängigen Prolog-Solver sollten bedeutend besser sein als alles, was man mal eben so zusammen schustert.

[Dejan Vu]

Zitat:

Zitat von BUG (Beitrag 1262643)

Die gängigen Prolog-Solver sollten bedeutend besser sein als alles, was man mal eben so zusammen schustert.

NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.

Da Rekursion einer der zentralen Deklarationsmetapher von Prolog ist, dürfte die Implementierung auch alles andere als Obersuperoptimal sein, obwohl ein Prolog-Interpreter tail recursion iterativ auflösen sollte.

Prolog wird teilweise bei Expertensystemen eingesetzt, sodass man hier prüfen müsste, inwieweit der TE ein derartiges System benötigt.

[BUG]

Zitat:

Zitat von Dejan Vu (Beitrag 1262644)

NP-Komplett bleibt NP-Komplett, egal in welcher Sprache. Sofern Du in Prolog keine Optimierungen (pruning) formulierst, wirst Du genauso lange warten.

Stimmt, ich war ein bisschen verwirrt :wink: :mrgreen:

[Dejan Vu]

Zitat:

Zitat von BUG (Beitrag 1262652)

Stimmt, ich war ein bisschen verwirrt :wink: :mrgreen:

Kein Wunder, bei dem Thread :stupid:

[juniorA]

Zu Beitrag 17
Nein ganz so einfach ist dieses nicht.
Ich habe maximal 99 Teillängen. Diese will ich auf Paletten legen die eine Länge von 12 Metern haben. Mir geht es jetzt darum, dass ich diese Teile so kombiniere, dass ich möglichst wenige Paletten brauche. Hinzu kommt noch folgende Schwierigkeit dass ich in der Mitte eines Abstellung habe wo das letzte Teil von der 1. Hälfte der Belegung maximal um 40 cm überstehen darf. Teile, deren Länge > 6.4 m sind, fallen von vorne sowieso raus.

:(

[Dejan Vu]

0/1-Knapsack-Problem. NP-Komplett. Kannste nicht durchprobieren. Aber Gott-Sei-Dank kann man das wohl mit linearer Programmierung lösen (wenn die Werte ganzzahlig sind).

[BUG]

Zitat:

Zitat von Dejan Vu (Beitrag 1262891)

Aber Gott-Sei-Dank kann man das wohl mit linearer Programmierung lösen (wenn die Werte ganzzahlig sind).

Diesmal bist du verwirrt: Lineare Programmierung mit Ganzzahlen ist im allgemeinen schwer; du meinst vermutlich dynamische Programmierung im Fall vom Rucksack-Problem.
Rucksack-Problem sehe insgesamt auch nicht: Es sollen schließlich keine Teillängen zu hause bleiben und man hat mehrere Paletten.

Mir sieht das eher nach der Optimierungsvariante von Bin-Packing auf: Fülle irgendwas in Behälter, so dass diese nicht überfüllt sind und du möglichst wenig Behälter brauchst. (@juniorA: Passt das auf dein Problem?)
NP-schwer, aber die Approximationsalgorithmen sind nicht so schlecht.

[Dejan Vu]

Zitat:

Zitat von BUG (Beitrag 1262950)

Diesmal bist du verwirrt: Lineare Programmierung mit Ganzzahlen ist im allgemeinen schwer; du meinst vermutlich dynamische Programmierung im Fall vom Knapsack-Problem.

Au Backe. :oops: Was ich eigentlich sagen wollte: "Also ich wollte sagen, dass etwa zu dieser Zeit die Verwirrung durch die ähm ... und die Verwirrung wird all jene verwirren, die nicht wissen; niemand wird wirklich genau wissen, wo diese kleinen Dinge zu finden sind, die verknüpft sind mit einer Art von Handarbeitszeug, das durch die Verknüpfung verknüpft ist; und zu der Zeit soll ein Freund seines Freundes Hammer verlieren und die Jungen sollen nicht wissen, wo die Dinge die jene Väter erst um 8 Uhr am vorhergehenden Abend dorthin gelegt hatten, kurz vor Glockenschlag."

[Bjoerk]

Zitat:

Zitat von juniorA (Beitrag 1262880)

[..]Ich habe maximal 99 Teillängen. Diese will ich auf Paletten legen die eine Länge von 12 Metern haben. Mir geht es jetzt darum, dass ich diese Teile so kombiniere, dass ich möglichst wenige Paletten brauche. Hinzu kommt noch folgende Schwierigkeit dass ich in der Mitte eines Abstellung habe wo das letzte Teil von der 1. Hälfte der Belegung maximal um 40 cm überstehen darf. Teile, deren Länge > 6.4 m sind, fallen von vorne sowieso raus. :(

Ich gehe bei diesen Problemen meistens so vor, daß ich das Größte auf den Stapel lege. Passt es nicht mehr rein dann in den nächsten Stapel bzw. einen neuen Stapel aufmachen. Das Verlegte aus der Liste rauslöschen. Das ganze solange bis die Liste leer ist. Das mit der Abstellung habe ich nicht verstanden?

[Dejan Vu]

Zitat:

Zitat von Bjoerk (Beitrag 1262956)

Das mit der Abstellung habe ich nicht verstanden?

Na. Es sind nicht 12m, sondern 2x6m mit der Einschränkung, das die ersten 6m um maximal 40cm überfüllt sein dürfen. Das schränkt die Möglichkeiten vielleicht ein, aber ich würde das trotzdem analytisch, d.h. mit dynamischer Programmierung machen. Wenn man nicht weiß, wie das geht (ich z.B.) dann schaue ich, ob ich das verstehe und wenn nicht, hol ich mir einen Experten oder einen Studenten von der Uni.