Kombinatorik - Index von Kombinationen

[Amateurprofi]

Ich erstelle eine Liste der Kombinationen von N Elementen zur 3ten Klasse und möchte den Index einer bestimmten Kombination ermitteln.
Die Elemente sind 0, 1, 2 … N-1.
Der Index soll 0-basierend sein.
Beispiel N=5

Code:

I  A B C
0) 0 1 2
1) 0 1 3
2) 0 1 4
3) 0 2 3
4) 0 2 4
5) 0 3 4
6) 1 2 3
7) 1 2 4
8) 1 3 4
9) 2 3 4

Für N Elemente zur 2ten Klasse habe ich folgende Funktion

Delphi-Quellcode:

FUNCTION CombiIndex2(N,A,B:Integer):Integer;
var H:Integer;
begin
   if A>B then begin
      H:=A;
      A:=B;
      B:=H;
   end;
   Result:=(((N+N-1-A)*A) shr 1) + B-A - 1;
end;

Die habe vor mehr als 20 Jahren erstellt und kann heute nicht mehr nachvollziehen wie ich darauf gekommen bin (wohl 'ne Altersdemenz) , und schaffe es auch nicht, eine entsprechende Funktion für Kombinationen zur 3-ten Klasse zu schreiben. Ich stehe da irgendwie auf dem Schlauch.

Frage:
Kennt jemand eine Lösung wie man den Index einer bestimmten Kombination in der Liste der Kombinationen von N Elementen zur 3ten Klasse ermitteln kann oder noch besser eine allgemeine Lösung für beliebige Klassen. Die Lösung soll natürlich nicht sein, die Liste der Kombinationen zu erstellen und dann zu suchen.

[Michael II]

Hallo APro,

wenn du für ein gegebenes n und ein Element intar:array of integer den Index ermitteln willst, dann könntest du es so tun:

Delphi-Quellcode:

type Tintarray = array of integer;


function indexvon( n : integer; intar : Tintarray ) : integer;
var hi, i, j, ind, k, firstel : integer;
begin
  ind := 0;
  k := length( intar );

  for hi := 0 to k-1 do
  begin
    firstel := intar[hi];
    for i := 0 to firstel-1 do inc( ind, tief( n-i-1, k-hi-1 ) );
    for j := hi+1 to k-1 do intar[j] := intar[j]-firstel-1;
    n := n-firstel-1;
  end;

  Result := ind;
end;

Wenn du umgekehrt für gegebene n, k und einen Index das Element ermitteln möchtest, dann kannst du es so tun:

Delphi-Quellcode:

function get_elem_fromindex( n, k, index : integer ) : Tintarray;
var lastind, hi, i, ind, firstel : integer;
    intar : TIntArray;
begin
  ind := 0;
  Setlength( intar, k );

  for hi := 0 to k-1 do
  begin
    i := 0;
    repeat
      lastind := ind;
      inc( ind, tief( n-i-1, k-hi-1 ) );
      inc(i);
    until ind > index;
    firstel := i-1;
    ind := lastind;
    intar[hi] := firstel;
    if hi > 0 then inc(intar[hi], intar[hi-1]+1 );
    n := n-firstel-1;
  end;

  Result := intar;
end;

Testen kannst du die ganze Sache so:

Delphi-Quellcode:

procedure TForm126.Button1Click(Sender: TObject);
var ar : TINtArray;
    anzahlelemente,
    test, i : integer;
    n, k : integer;

begin
   // zum Beispiel für deinen Fall n=5, k=3:
  n := 5;
  k := 3;

  SetLength( ar, k );

  anzahlelemente := 0;
  for i := 0 to n-k do inc( anzahlelemente, tief( n-i-1, k-1 ) ); // so viele Elemente enthält deine "k aus n Liste"

  // wir testen alle Fälle durch:
  for i := 0 to anzahlelemente-1 do
  begin
      ar := get_elem_fromindex( n, k, i ); // wir ermitteln aus dem Index das Listenelement
      test := indexvon( n, ar ); // für gegebenes n und Element ar wird der Listenindex berechnet
      if i <> test then Showmessage( 'fehler' );
  end;
end;

Im Code oben gilt:
tief(n,k) = n!/k!/(n-k)!

Der Code lässt sich sicher schöner schreiben - ich hatte es etwas eilig .

[Amateurprofi]

@Michael II

Danke für deine Hilfe, deine "indexvon" Funktion liefert korrekte Ergebnisse ist aber nicht so ganz das, was ich suche.
Warum:
Die Funktion arbeitet mit 2 Schleifen und braucht bei etwas größerem N einfach zu lange.
Vielleicht habe ich meine Frage zu allgemein gestellt, deshalb etwas präziser und etwas Hintergrundinfo. Sorry, wird etwas langatmig.

Ich hatte vor vielen Jahren ein Programm geschrieben das u.a. Endspieltabellen für Schach erstellen kann, allerdings nur für einige wenige Endspiele, in der Regel 4-Steiner, und als einzige 5-Steiner Tabelle für das Endspiel König und 2 Springer gegen König und Bauer.

Ich möchte jetzt Tabellen für alle 3, 4, 5 und später eventuell 6 Steiner erstellen.
Es gibt ja frei zugängliche 6-Steiner Tabellen (www.shredderchess.de) oder auch 7-Steiner (google play store - leider nur übers Smartphone), aber die kann ich nicht in ein eigenes Programm einbinden und, wichtiger, mir geht’s ums "machen", nicht ums "nutzen".

Das Problem bei der Erstellung ist weniger der Algorithmus sondern mehr die Größe der Tabellen.

Die Größe der Tabelle für ein bestimmtes Endspiel hängt ja davon ab, wieviel verschiedene mögliche Stellungen existieren.

Bei einem 5-Steiner kann man im ersten Schritt von 64^5 = 1,073,741,824 Stellungen ausgehen.
Die erste Optimierung ist, dass man nicht alle Stellungen betrachtet sondern nur solche bei denen der weiße König im Dreieck A1-D1-D4 steht, bzw. im Rechteck A1-D1-D8-A8, wenn Bauern im Spiel sind und bei denen die Könige nicht auf benachbarten Feldern stehen.
Das reduziert die Anzahl der möglichen Stellungen der beiden Könige von 4096 auf 564 bzw. auf 1806.

Eine weitere Optimierung ist möglich, wenn eine Partei 2 oder mehr gleiche Figuren hat.
Dann kann man davon ausgehen, dass immer die erste der Figuren auf dem "niedrigsten" Feld steht und die letzte auf dem "höchsten".
Bei zum Beispiel 3 gleichen Figuren kann dadurch die Anzahl der möglichen Stellungen für diese 3 Figuren von 64^3 = 262,144 auf (64 über 3) = 41,664 reduziert werden.

Alle diese Optimierungen reduzieren die die Größe der Tabelle für z.B. das Endspiel König + 3 Springer gegen König von 64^5 = 1,073,741,824 Bytes auf 564*(64 über 3) = 23,498,496 Bytes.

Allerdings braucht man eine schnell arbeitende Funktion für die Ermittlung der Indizes von Kombinationen, denn diese Funktion wird milliardenfach aufgerufen.
Na klar kann man das auch sehr schnell mit Tabellen machen, und das ist das, was ich zur Zeit mache, aber spätestens bei 6-Steinern (was Kombinationen der 4ten Klasse bedeutet) wird es eng mit dem Speicherplatz.

Vielleicht fällt dir ja bei der geänderten Fragestellung (Kombinationen mit 64 Elementen zur 3ten Klasse) etwas ein.

[Bjoerk]

Ich würde es aber genau so machen. Eine Klasse TNofM (IntegerList), die N aus M ausrechnen und in Filestreams schreiben. Die App liest die dann ein. Warum denn nicht?

[Amateurprofi]

Zitat von Bjoerk:

Ich würde es aber genau so machen. Eine Klasse TNofM (IntegerList), die N aus M ausrechnen und in Filestreams schreiben. Die App liest die dann ein. Warum denn nicht?

Ja, jeder wie er mag. Du lieber mit FileStreams, ich lieber mit Mathe...

Zitat von Bjoerk:

Warum denn nicht?

Weil ich keine Daten aus Dateien lesen will, die sehr viel schneller errechnet werden können.
Die in #1 gezeigte Funktion zeigt, dass das Errechnen des Indexes einer Kombination zumindest für die 2te Klasse funktioniert und zwar blitzschnell, und ich gehe davon aus, dass das auch für die 3te Klasse geht - weiß nur noch nicht, wie.

[Michael II]

Hallo APro


danke für dein Feedback.

Ich wollte zeigen, wie sich der Index allgemein für n,k und gegebenes Listenelement l berechnen kann - und damit deine Frage nach dem n,k Fall beantworten.

Für Spezialfälle wie dein "n=5 k=3" Fall lässt sich die gegebene Prozedur natürlich (durch Einsetzen der Werte für n und k in meiner indexvon Funktion) vereinfachen.
( In Extremis könntest du natürlich durch case oder if sämtliche Fälle abdecken und hättest dann bei k = 3 sonst nur noch 2 Additionen. )

Du schreibst, dass die indexvon für grosse n sehr langsam wäre. Hast du das getestet oder erahnt? Die Kpmplexität beträgt ja hier nur k (Schleife aussen) mal n (maximal für Schleife innen - im Maximalfall n, genau dann wenn im Listenelement das letzte Arrayelement n-1). Hinweis: Die "tief-Werte" kannst du tabellieren.


Gruss
M

[Michael II]

Delphi-Quellcode:

var hsum : array[0..64, 0..7] of integer;
// Summen berechnen

procedure berechnesummen;
var n, k : integer;
begin
  for n := 0 to 64 do
    for k := 0 to 7 do
    begin
      if ( k=0 ) or ( k=n ) then hsum[n,k] := 1
      else
      hsum[n,k] := hsum[n-1,k-1] + hsum[n-1,k];
    end;
end;


function indexvon2( n : integer; intar : Tintarray ) : integer;
var i, ind, k : integer;
begin
  ind := 0;
  k := length( intar );
  for i := k-1 downto 1 do intar[i] := intar[i]-intar[i-1]-1;

  for i := 0 to k-1 do
  begin
    inc( ind, hsum[n,k] - hsum[n-intar[i],k] ); // [3]
    dec( k );
    n := n - intar[i] - 1;
  end;

  Result := ind;
end;

Hallo Apro

hier noch eine sehr schnelle Art zur Berechnung (keine Multiplikation, Aufwand nur abhängig von k) der Indices (siehe oben : indexvon2). Viel schneller geht's wohl nicht.

In der vorher geposteten Lösung wurden Summen wie zum Beispiel
[1] tief(n-1,k-1) + tief(n-2,k-1) + ... tief(n-a,k-1) immer wieder neu berechnet. (Die innere Schleife).

In indexvon2 wird jetzt ausgenutzt, dass Summe
[2] tief(n-1,k-1) + .... + tief(k-1,k-1) = tief(n,k).

Du kannst also [1] berechnen, indem du von [2] die Summe tief(n-a-1,k-1)+...+tief(k-1,k-1) abziehst. Im Code oben mit [3] markiert.


Wie erwähnt: Für feste n,k kannst du indexvon2 direkt durch Einsetzen der festen Werte vereinfachen.

Delphi-Quellcode:

procedure TForm126.Button1Click(Sender: TObject);
var ar : TINtArray;
    anzahlelemente,
    test, i : integer;
    n, k : integer;

    hs : TStringList;
    xs : string;
  x: Integer;

begin
  hs := TStringList.Create;

  n := 20;
  k := 5;

  berechnesummen; // Summen werden nur einmal berechnet

  SetLength( ar, k );

  anzahlelemente := tief( n, k );

  for i := 0 to anzahlelemente-1 do
  begin
      ar := get_elem_fromindex( n, k, i );

      xs := '';
      for x := 0 to k-1 do xs := xs + ar[x].ToString + ' ';
      xs := i.ToString + ' ' + xs;
      hs.Add( xs );

      test := indexvon2( n, ar );
      if i <> test then Showmessage( 'fehler' );
  end;

  hs.SaveToFile( 'C:\Users\Michael\Desktop\check.txt' );
  hs.Free;

end;

Viel Spass.

Gruss
M


Ach ja... der umgekehrte Fall Index -> Array Element liesse sich natürlich auch vereinfachen... im oben geposteten Code hatte es noch einen kleinen Bug. Korrekt ist:

Delphi-Quellcode:

function get_elem_fromindex( n, k, index : integer ) : Tintarray;
var lastind, hi, i, ind, firstel : integer;
    intar : TIntArray;
begin
  ind := 0;
  Setlength( intar, k );

  for hi := 0 to k-1 do
  begin
    i := 0;
    repeat
      lastind := ind;
      inc( ind, tief( n-i-1, k-hi-1 ) );
      inc(i);
    until ind >= index;

    if ind > index then
    begin
      firstel := i-1;
      ind := lastind;
    end
    else
    begin
      firstel := i;
    end;

    intar[hi] := firstel;
    if hi > 0 then inc(intar[hi], intar[hi-1]+1 );
    n := n-firstel-1;
  end;

  Result := intar;
end;

[Amateurprofi]

@Michael II

Ja klar, kann man das für ein bestimmtes K vereinfachen, aber es bleibt die innere Schleife für N=64.
Mein Beispiel für N=5, K=3 war ja nur um aufzuzeigen wie die Liste der Kombinationen aussieht.
Hätte ich solch eine Liste für N=64 K=3 hier rein gestellt, wäre das etwas unübersichtlich gewesen (41664 Zeilen).

Zitat von Michael II:

Du schreibst, dass die indexvon für grosse n sehr langsam wäre. Hast du das getestet oder erahnt?

Ich hatte das weder getestet noch erahnt sondern "gesehen".
Ich hatte auch nicht geschrieben die indexvon sei für große n sehr langsam.
Was ich schrieb war, "braucht bei etwas größerem N einfach zu lange" (gemeint: für meine Zwecke zu lange).
Tatsächlich arbeitet sie recht flink.
Stell dir jemanden vor, der 100 m in 9.27 s läuft.
Dann ist der verdammt schnell, denn schneller geht es nicht. https://de.wikipedia.org/wiki/100-Meter-Lauf
Aber um in Hamburg zu Frühstücken und in Paris Mittag zu Essen reicht es trotzdem nicht.

Ich hab mal Spaßeshalber die indexvon mit der CombiIndex2 aus #1 am Beispiel N=64 K=2 verglichen. Die indexvon braucht etwa 50 mal so lange.
Dann hab ich versucht die HI-Schleife in der indexvon aúfzulösen.
Bei N=64 und K=2 kam dann letztendlich ein Einzeiler heraus - quasi identisch mit der CombiIndex2.

Tja, und dann habe ich versucht das Gleiche für K=3 zu machen.
Beim ersten Durchlauf (HI=0) konnte ich
for i := 0 to firstel-1 do inc( ind, tief( n-i-1, k-hi-1 ) );
durch Result := (A * (A*A - 189*A + 11906))/6; wobei A identisch ist mit intar[0]
ersetzen.
Aber beim zweiten durchlauf (HI=1) wurde schnell klar, dass es so einfach nicht ist, weil N um intar[0]+1 gesenkt wurde.
Deshalb müßte ich tatsächlich mit case Strukturen arbeiten, oder mit einer kleinen Tabelle.
Aber das mache ich ja jetzt auch schon. Und wenn das Ergebnis ist, dass die Tabelle nur "etwas" kleiner ist, dann macht das für mich keinen Sinn.
Ich bleibe also vorerst (für die 5 Steiner-Tabellen) bei dem was ich schon habe, und wenn ich mich dann irgenwann an die 6-Steiner mache, schau ich mir das wieder an.

Nochmal: Herzlichen Dank für die Mühe die du dir gemacht hast.

[Michael II]

Hallo Apro

Wenn du in indexvon k=2 wählst, dann erhältst du natürlich genau deine Berechnung "CombiIndex2".

Denn für k=2 und ein Listenelement l=(a,b) gilt
(1.) ind(l) = tief(n,2)-tief(n-a,2) + tief(n-a-1,1)-tief(n-b,1)

Du hattest nach einer Herleitung für den Fall k=2 gefragt: Wenn du für l=(a,b) den Index berechnen willst, dann musst du berechnen, wieviele Listenelemente (x0,x1) vor l=(a,b) in der Liste stehen.

Es gibt n-1 Elemente mit (0,x1), n-2 Elemente mit (1,x1),... und (n-a-1) Elemente mit (a-1,x1), welche vor (a,x1) stehen.
Und wieviele Elemente (a,x1) stehen vor (a,b)? Es sind b-a-1.

Insgesamt liegen also s = (n-1)+(n-2)+...+(n-a-1) + b-a-1 vor (a,b).
Vereinfachen bringt: s = n*(n-1)/2+(n-a)*(n-a-1)/2+b-a-1 = a*(2n-a-1)/2 + b-a-1

Für grössere Werte von k wird die explizite Berechnung wie in deiner Funktion CombiIndex2 rasch aufwändiger und benötigt somit mehr Zeit.

Für k=3 und ein Listenelement l=(a,b,c) ergibt sich zum Beispiel
(2.) ind(l) = n*(n-1)*(n-2)/6 - (n-a)*(n-a-1)*(n-a-2)/6+ (n-a-1)*(n-a-2)/2 - (n-b)*(n-b-1)/2 + ( n-b-1) - (n-c)
Dieser Term lässt sich etwas [immer unter Berücksichtigung, dass die Summanden ganzzahlig bleiben sollen damit du ganzzahlig rechnen kannst] vereinfachen, aber du siehst auch so, dass der Aufwand deutlich steigt. (Maple oder Mathematica oder ein guter Taschenrechner helfen sicher weiter .]

Du hattest nach einer allgemeinen Formel gefragt.
Für gegebenes n, k und Listenelement L=( a0, a1, ..., a[k-1] ), a0<a1<...<a[k-1] gilt für den Index ind von L:

(3.) ind(l) = tief(n,k) - tief(n-a0,k) // so viele Listenelemente (x0,...), x0<a0 gibt es
+ tief(n-a0-1,k-1) - tief(n-a1,k-1) // so viele Listenelente (a0,x1,...), x1<a1 gibt es
+ tief(n-a1-1,k-2) - tief(n-a2,k-2) // so viele Listenelente (a0,a1,x2...), x2<a2 gibt es
+ ....
+ tief(n-a[k-2]-1,1) - tief(n-a[k-1],1) // so viele Listenelemente (a0,a1,a2,...,a[k-2],x[k-1]), x[k-1]<a[k-1] gibt es


(3.1) Zu Zeile 1 in (3.): Es liegen s = tief(n-1,k-1) + tief(n-2,k-1) +... + tief(n-a0,k-1) Elemente vor (a0,...)
Wir wissen summe(i=k-1..n-1, tief(i,k-1) ) = tief(n,k). In (3.1) verwendet erhalten wir s= tief(n,k) - tief(n-a0,k).


Für grössere k lohnt es sich, gewisse Werte zu tabellieren; zum Beispiel so:

Delphi-Quellcode:

var hsum : array[0..64, 0..7] of integer;
    hdelta : array[0..64, 0..64, 0..7] of integer;

procedure berechnesummen;
var n, n2, k : integer;
begin
  // Berechnung von tief(n,k)
  for n := 0 to 64 do
    for k := 0 to 7 do
    begin
      if ( k=0 ) or ( k=n ) then hsum[n,k] := 1
      else
      hsum[n,k] := hsum[n-1,k-1] + hsum[n-1,k];
    end;

  // Berechnung von tief(n,k)-tief(n2,k)
  for n := 0 to 64 do
    for n2 := 0 to n do
      for k := 0 to 7 do
       begin
          hdelta[n,n2,k] := hsum[n,k] - hsum[n2,k];
       end;
end;

hdelta in (3.) eingesetzt ergibt:

(4.) ind(l) = hdelta[n,n-a0,k]
+ hdelta[n-a0-1,n-a1,k-1]
+ hdelta[n-a1-1,n-a2,k-2]
+ ....
+ hdelta[n-a[k-2]-1,n-a[k-1],1]


Wie du schreibst, ist für k=2 die direkte Berechnung (1.) schneller als indexvon3. Für k=3 ist indexvon3 bereits in etwa gleich schnell wie die Berechnung aus (2.).

Delphi-Quellcode:

type Tintarray = array of integer;

function indexvon3( n : integer; const intar : Tintarray ) : integer;
var i, ind, k : integer;
begin
  ind := 0;
  k := length( intar );

  ind := hdelta[n,n-intar[0],k];
  for i := 1 to k-1 do
    inc( ind, hdelta[n-intar[i-1]-1,n-intar[i],k-i] );

  Result := ind;
end;

Die Berechnung wie in "indexvon3" liesse sich sicher weiter optimieren.