Kombinatorik - Index von Kombinationen

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