Kombinationen als Index

[efknarf]

Hallo,

mal eine Frage an unsere Mathematiker im Forum. Ich suche eine Idee/ Formel oder Routine, mit der ich eine Kombination (Kombination ohne Wiederholung) von Werten in einen Index überführen kann bzw. diesen Index wieder in die entsprechede Kombination zurückübertragen kann.

Beispiel: 2 aus 3
Menge: 123
12 --> 0
13 --> 1
23 --> 2

Beispiel: 3 aus 10
Menge: 'abcdefghij'

'abc' --> 0
'abd' --> 1
'abe' --> 2
.
.
.
'hij' --> 119

Wie aber sieht es aus, wenn die Kombinationen aus Elementen von 10 aus 30 oder noch mehr bestehen? Dann ist die Umwandlung nicht mehr so einfach. In diesem Fall hatte ich bisher ein Array, in welchem ich die Kombination suchte und den Index so ermittelte. Der Speicheraufwand ist bei größeren Kombinationen aber enorm, mal abgesehen davon, dass es eine Weile dauert, bis das Array erstellt und entsprechend sortiert ist und der richtige Eintrag gefunden wurde.

Iteratives Ermitteln der Kombination mit Erhöhung eines Zählwertes dauert zu lange und ist auch nicht besonders schlau. Hat jemand eine Idee, wie man den Index einer Kombination etwas cleverer ermitteln kann?

Delphi-Quellcode:

function Kombi_to_Index_K_aus_N(K,N: Byte; const AKombination: TKombination): Integer;
function Index_to_Kombi_K_aus_N(K,N: Byte; Index: Integer): TKombination;

[shmia]

Permutation

[efknarf]

Danke für die schnelle Antwort, aber auf der Suche war ich da auch schon. Das hilft mir nicht wirklich, da ich kein Mathematiker bin und ich nicht so richtig weiß, was ich mit den Stirling-Zahlen beginnen soll. Irgendwie sagt mir mein Gefühl, das ich sie benötige - ich weiß bloß nicht wo und was ganz wichtig ist - wie.

[Uwe Raabe]

Nach meinem Verständnis der Stirling-Zahlen sind die ganz und gar nicht, was du brauchst.

Wenn ich dich richtig verstehe, suchst du eine Möglichkeit, die möglichen Kombinationen in einer bestimmten Reihenfolge aufzuzählen. Damit kann jeder Permutation eine feste Zahl zwischen 0 und M-1 (M = Anzahl der Kombinationen) zugeordnet werden. Nun brauchst du einen Algorithmus, der zu einer gegebenen Kombination diese Zahl ermittelt bzw. umgekehrt anhand der Zahl die entsprechende Kombination zurückliefert.

Ich bin nicht sicher, ob das mit vertretbarem Aufwand überhaupt möglich ist, aber das Ganze steht und fällt mit einer geschickten Anordnung der Kombinationen. Leider fällt mir da spontan keine Lösung ein, aber vielleicht hat ja jemand anderes da eine geniale Idee?

Gruß, Uwe

[efknarf]

Genau so ein Algorithmus oder eine Idee ist gefragt! Und:
Stimmt! Stirling ist es nicht! Hab mich geirrt. Aber ich konnte herausfinden, dass die Zahlenfolgen im Pascal-Dreieck damit zu tun haben. Wenn ich nämlich eine überschaubare Menge aufschreibe und auf bestimmte Weise gruppiere und zähle, ergeben sich die Zahlenfolgen, wie sie auch im besagten Dreieck errechnet werden.

Beispiel: 5 aus 8
ergibt nach Gruppierung:
4*1+
3*4+
2*10+
1*20=56
wobei die Zahlenfolge 1,4,10,20 in einer der Diagonalen im Pascal-Dreieck vorkommt.

Beispiel: 4 aus 8
ergibt nach Gruppierung:
5*1+
4*3+
3*6+
2*10+
1*15=70
wobei die Zahlenfolge 1,3,6,10,15 in einer der Diagonalen im Pascal-Dreieck vorkommt.

Habe aber noch keine Ahnung, wie ich das gewinnbringend verwenden kann.

[efknarf]

Schade! Hat wirklich niemand eine Idee?

Macht nichts! Habe selbst einen Algorithmus entwickelt, mit welchem ich zumindest eine Kombination in einen Index umwandeln kann. Nach dem mein Schreibtisch nun unter der Last der vollgekritzelten Blätter fast zusammenbricht, habe ich die Lösung!
Und es ist so einfach!
Werde diesen Algorithmus aber erst in eine Funktion verpacken und ausgiebig testen, bevor ich diesen öffentlich mache. Denn vielleicht freue ich mich ja auch zu früh.
Der Programmieraufwand, soviel kann ich schon sagen, ist nicht so groß, wie man erwarten würde.

Trotzdem sind auch weiterhin Ideen gefragt, denn auch wenn mein Algo funktioniert, muß das nicht heißen, dass es nicht auch noch besser kann.

Bye

[Blup]

Das Problem erschien mir interessant genug, um eine Klasse zu erstellen, die sich damit beschäftigt.
Die entsprechende Unit gibts als Dateianhang.

[efknarf]

Danke sehr.
Haste alles schon so gemacht, dass man es gleich verwenden kann. Finde ich Super!
Werde es dann mal testen. Sieht sehr interessant aus.

Bye

[alzaimar]

Stichwort: Graycodes
Hier eine Kopie eines Beitrages von mir aus dem Delphi-Forum;
Man kann Permutationen aufzählen. Dazu schreibt man alle Permutationen auf. Anschließend schreibt man neben jede Permutation den Inverse-Code: Für jedes Zeichen wird die Anzahl der Zeichen gezählt, die rechts vom Zeichen vorkommen und größer sind.
Jede Stelle i dieses Codes wird nun mit (i-1)! multipliziert (von rechts zählen). Wir erhalten die Zahlen von 0 bis n!-1 (n=Anzahl der Stellen). Damit haben wir eine Ordnung auf den Permutationen

• 321 000 0
  312 010 1
  231 100 2
  213 110 3
  132 200 4
  123 210 5

Hier der Algorithmus, der aus einer Zahl die korrespondierende Permutation erstellt. Die Umkehrfunktion (Permutation->Index) kannst Du nach o.g. Schema leicht selbst implementieren.

Delphi-Quellcode:

Function NthPermutation (aString : String; aCount : Integer) : String;
Var
  d : Array Of Integer;
  g, i, n : Integer;

Begin
  n := Length (aString);
  setlength (d, n);
  d[1] := 1;
  For i := 2 to n - 1 do d[i] := i * d[i-1];
  Result := '';
  for i := n-1 downto 1 do begin
    g := (aCount div d[i]) + 1;
    Result  := Result  + aString[g];
    delete (aString, g, 1);
    aCount := aCount mod d[i];
    End;
  Result := Result  + aString;
End;