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.