Kombinatorik - Index von Kombinationen

[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.